【单源最短路径】dijkstra+SPFA模板题

2018年11月30日 0条评论 533次阅读 0人点赞于衡

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入输出格式

输入格式：

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出格式：

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

输入输出样例

输入样例#1： 复制

输出样例#1： 复制

0 2 4 3

说明

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=15；

对于40%的数据：N<=100，M<=10000；

对于70%的数据：N<=1000，M<=100000；

对于100%的数据：N<=10000，M<=500000。保证数据随机。

对于真正 100% 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。

样例说明：

图片1到3和1到4的文字位置调换

迪杰斯特拉解法：

#include <bits/stdc++.h>

using namespace std;
const int INF=2147483647;
const int MAXN=1000010;
struct qnode
{
    int v;
    int c;
    qnode(int v=0,int c=0):v(v),c(c){}
    bool operator <(const qnode &r)const
    {
        return c>r.c;
    }
};
struct Edge
{
    int v,cost;
    Edge(int v=0,int cost=0):v(v),cost(cost){}
};
vector<Edge>E[MAXN];//图
bool vis[MAXN];
int dist[MAXN];
void Dijkstra(int n,int start)//点的编号从1开始
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)dist[i]=INF;
    priority_queue<qnode>que;
    while(!que.empty())que.pop();//初始化
    dist[start]=0;
    que.push(qnode(start,0));
    qnode tmp;
    while(!que.empty())
    {
        tmp=que.top();
        que.pop();
        int u=tmp.v;
        if(vis[u])continue;
        vis[u]=true;
        for(int i=0;i<E[u].size();i++)
        {
            int v=E[tmp.v][i].v;
            int cost=E[u][i].cost;
            if(!vis[v]&&dist[v]>dist[u]+cost)
            {
                dist[v]=dist[u]+cost;
                que.push(qnode(v,dist[v]));
            }
        }
    }
}
void addedge(int u,int v,int w)
{
    E[u].push_back(Edge(v,w));
}
int main()
{
    int n,m,s;
    int T;
 
        scanf("%d%d%d",&n,&m,&s);
        for(int i=1;i<=n;i++)E[i].clear();
        for(int i=0;i<m;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
            //addedge(v,u,w);无向图
        }
        Dijkstra(n,s);
        //单源最短路，dist[i]为从源点start到i的最短路
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            cout<<dist[i]<<' ';
        }
        
    return 0;
}

SPFA解法：

#include<iostream>
#include<cstdio>
#include<queue>
#include<queue>
#include<cstring>

using namespace std;

const int MAXN=1000010;
//const int INF=0x3f3f3f3f;
const int INF=0x7fffffff;

struct edge{
  int v,cost;
  edge(int _v,int _cost):v(_v),cost(_cost){}
};
vector<edge>E[MAXN];

void add_edge(int u,int v,int w)
{
  E[u].push_back(edge(v,w));
}

bool vis[MAXN];
int cnt[MAXN];
int dist[MAXN];

bool spfa(int start,int n)
{
  memset(vis,false,sizeof(vis));
  for(int i=1;i<=n;i++){
    dist[i]=INF;
  }
  vis[start]=true;
  dist[start]=0;
  queue<int>que;
  while(!que.empty()){
    que.pop();
  }
  que.push(start);
  memset(cnt,0,sizeof(cnt));
  cnt[start]=1;
  while(!que.empty()){
    int u=que.front();
    que.pop();
    vis[u]=false;
    for(int i=0;i<E[u].size();i++){
      int v=E[u][i].v;
      if(dist[v]>dist[u]+E[u][i].cost){
        dist[v]=dist[u]+E[u][i].cost;
        if(!vis[v]){
          vis[v]=true;
          que.push(v);
          if(++cnt[v]>n){
            return false;
          }
        }
      }
    }
  }
  return true;
}

int main()
{
  int n,m,s;
  int T;

  scanf("%d%d%d",&n,&m,&s);
  for(int i=1;i<=n;i++)E[i].clear();
  for(int i=0;i<m;i++)
  {
    int u,v,w;
    scanf("%d%d%d",&u,&v,&w);
    add_edge(u,v,w);
    //addedge(v,u,w);无向图
  }
  spfa(s,n);
  //单源最短路，dist[i]为从源点start到i的最短路
  int ans=0;
  for(int i=1;i<=n;i++)
  {
    cout<<dist[i]<<' ';
  }

  return 0;
}