SPFA

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <queue>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn = 500003;
 8 struct node
 9 {
10     int next , to , w;
11 }G[maxn];
12 int head[maxn] , tail;
13 int n , m;
14 int dis[maxn] , used[maxn];
15 queue <int> q;
16 void add(int u , int v , int w)
17 {
18     tail++;
19     G[tail].next = head[u] , G[tail].to = v , G[tail].w = w;
20     head[u] = tail;
21 }
22 void SPFA(int start)
23 {
24     for(int i = 1; i <= n; i++)
25         dis[i] = 2147483647;
26     dis[start] = 0;
27     q.push(start) , used[start] = 1;
28     while(!q.empty())
29     {
30         int now = q.front(); 
31         q.pop();
32         used[now] = 0;
33         for(int i = head[now]; i ; i = G[i].next)
34         {
35             if(dis[now] + G[i].w < dis[G[i].to])
36             {
37                 dis[G[i].to] = dis[now] + G[i].w;
38                 if(!used[G[i].to])
39                     q.push(G[i].to) , used[G[i].to] = 1;
40             }
41         }
42     }
43 }
44 int main()
45 {
46     int start , u , v , w;
47     scanf("%d%d%d" , &n , &m , &start);
48     for(int i = 1; i <= m; i++)
49     {
50         scanf("%d%d%d" , &u , &v , &w);
51         add(u , v , w);
52     }
53     SPFA(start);
54     for(int i = 1; i <= n; i++)
55         printf("%d " , dis[i]);
56     return 0;
57 }