SPFA模板

没错，就是传说中deadSPFA的模板
 1 //
 2 //  SPFA模板.cpp
 3 //  algorithm
 4 //
 5 //  Created by david.xu on 2018/8/6.
 6 //  Copyright © 2018年 Amorphophallus-Konjac. All rights reserved.
 7 //
 8 
 9 #include <stdio.h>
10 #include <cstdlib>
11 #include <cstring>
12 #include <cmath>
13 #include <iostream>
14 #include <algorithm>
15 #include <queue>
16 #include <vector>
17 #define maxn 100010
18 
19 using namespace std;
20 
21 int n,m,s,dis[maxn];
22 bool vis[maxn];
23 
24 struct edge{
25     int val,to;
26 };
27 vector<edge> e[maxn];
28 
29 queue<int> q;
30 
31 void SPFA()
32 {
33     for(int i=1;i<=n;i++)
34         dis[i]=1000000001;
35     dis[s]=0;
36     q.push(s);
37     vis[s]=1;
38     while(!q.empty())
39     {
40         int x=q.front();
41         q.pop();
42         for(int i=0;i<e[x].size();i++)
43         {
44             int y=e[x][i].to;
45             if(dis[x]+e[x][i].val<dis[y])
46             {
47                 dis[y]=dis[x]+e[x][i].val;
48                 if(!vis[y])
49                 {
50                     q.push(y);
51                     vis[y]=1;
52                 }
53             }
54         }
55         vis[x]=0;
56     }
57 }
58 
59 int main()
60 {
61     scanf("%d%d%d",&n,&m,&s);
62     for(int i=1;i<=m;i++)
63     {
64         int x,y,z;
65         scanf("%d%d%d",&x,&y,&z);
66         edge tmp;
67         tmp.to=y;
68         tmp.val=z;
69         e[x].push_back(tmp);
70     }
71     SPFA();
72     for(int i=1;i<=n;i++)
73         printf("%d ",dis[i]);
74     return 0;
75 }