SPFA算法

 1 #include<cstdio>
 2 #include<cctype>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 const int inf=0x3f3f3f3f;
 7 int n,m,s,head[maxn],eid,d[maxn],inq[maxn],cnt[maxn];
 8 struct edge {
 9     int v,w,next;
10     edge(int v=0,int w=-1):v(v),w(w) {}
11 } E[maxm];
12 void init() { //还是不要忘记初始化！
13     memset(head,-1,sizeof(head));
14     memset(d,inf,sizeof(d));
15 }
16 void insert(int u,int v,int w) {
17     E[eid]=edge(v,w);
18     E[eid].next=head[u];
19     head[u]=eid++;
20 } //邻接表存储，时间和空间上都会提高效率
21 queue<int> q;
22 bool spfa() {
23     d[s]=0;
24     q.push(s); //初始先将源点入队
25     inq[s]=1;
26     while(!q.empty()) {
27         int u=q.front();
28         q.pop();
29         inq[u]=0;
30         for(int p=head[u];p+1;p=E[p].next) {
31             int v=E[p].v;
32             if(d[v]>d[u]+E[p].w) { //松弛
33                 d[v]=d[u]+E[p].w;
34                 if(++cnt[v]>=n) return false; //如果一个点被更新超过n-1次
35                 //说明存在负环，不存在最短路
36                 if(!inq[v]) { //结点不在队列中就可以入队
37                     q.push(v); //同一结点可能会多次入队
38                     inq[v]=1; //但不会同时出现在队列中
39                 }
40             }
41         }
42     }
43     return true;
44 }
45 int main() {
46     scanf("%d%d%d",&n,&m,&s);
47     init();
48     int u,v,w;
49     for(int i=1;i<=m;++i) {
50         scanf("%d%d%d",&u,&v,&w);
51         insert(u,v,w);
52     }
53     spfa();
54     for(int i=1;i<=n;++i) {
55         if(i!=1) putchar(‘ ‘);
56         printf("%d",d[i]);
57     }
58     return 0;
59 }