SPFA 模板

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <cstring>
 6 #include <string>
 7 #include <vector>
 8 #include <queue>
 9 using namespace std;
10 #define inf 0x3f3f3f3f
11 struct A
12 {
13     int ed;
14     int power;
15 };
16 vector <A> v[1000100];
17 int dis[1000100],vis[1000100];
18 int n,m;
19 queue<int> q;
20 void SPFA(int s,int n)
21 {
22     memset(dis,inf,sizeof(dis));
23     memset(vis,0,sizeof(vis));
24     dis[s]=0;vis[s]=1;
25     q.push(s);
26     while(!q.empty())
27     {
28         int u=q.front();
29         q.pop();vis[u]=0;
30         for(int i=0;i<v[u].size();i++)
31         {
32             int x=v[u][i].ed;
33             int y=v[u][i].power;
34             if(dis[u]+y<dis[x])
35             {
36                 dis[x]=dis[u]+y;
37                 if(vis[x]==0)
38                 {
39                     q.push(x);
40                     vis[x]=1;
41                 }
42             }
43         }
44     }
45     return;
46 }
47 int main()
48 {
49     cin>>n>>m;
50     int i,j,k;
51     for(i=0;i<m;i++)
52     {
53         int x,y,c;
54         cin>>x>>y>>c;
55         A t;
56         t.ed=y;t.power=c;
57         v[x].push_back(t);
58         t.ed=x;t.power=c;
59         v[y].push_back(t);
60     }
61     SPFA(0,n);
62     for(i=1;i<n;i++)
63         cout<<dis[i]<<endl;
64     return 0;
65 }