Dijkstra

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <queue>
 4 using namespace std;
 5 const int INF = 2147483647;
 6 const int maxn = 500003;
 7 int n , m , start;
 8 int dis[maxn] , used[maxn];
 9 struct node
10 {
11     int next , to , w;
12 }G[maxn];
13 struct Node
14 {
15     int dis , pos;
16     bool operator < (const Node &x) const
17     {
18         return x.dis < dis;
19     }
20 };
21 int head[maxn] , tail;
22 priority_queue <Node> q;
23 void add(int u , int v , int w)
24 {
25     tail++;
26     G[tail].next = head[u];
27     G[tail].to = v;
28     G[tail].w = w;
29     head[u] = tail;
30 }
31 void init()
32 {
33     for(int i = 1; i <= n; i++)
34         dis[i] = INF;
35     dis[start] = 0;
36 }
37 void Dijkstra()
38 {
39     q.push((Node){0 , start});
40     while(!q.empty())
41     {
42         Node now = q.top();
43         q.pop();
44         if(used[now.pos])
45             continue;
46         used[now.pos] = 1;
47         for(int i = head[now.pos]; i; i = G[i].next)
48         {
49             if(G[i].w + dis[now.pos] < dis[G[i].to])
50             {
51                 dis[G[i].to] = G[i].w + dis[now.pos];
52                 if(!used[G[i].to])
53                     q.push((Node){dis[G[i].to] , G[i].to});
54             }
55         }
56     }
57 }
58 int main()
59 {
60     int u , v , w;
61     scanf("%d%d%d" , &n , &m , &start);
62     for(int i = 1; i <= m; i++)
63     {
64         scanf("%d%d%d" , &u , &v , &w);
65         add(u , v , w);
66     }
67     init();
68     Dijkstra();
69     for(int i = 1; i <= n; i++)
70         printf("%d " , dis[i]);
71     return 0;
72 }