Dijkstra

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 using namespace std;
 5 int n,m,S,tot;
 6 int Next[500010],head[20000],tree[500010],val[500010];
 7 bool visit[20000];
 8 
 9 long long dis[20000];
10 
11 struct cmp{
12     bool operator()(int a,int b)
13     {
14         return dis[a]>dis[b];
15     }
16 };
17 priority_queue<int,vector<int>,cmp> Q;
18 void add(int x,int y,int z)
19 {
20     tot++;
21     Next[tot]=head[x];
22     head[x]=tot;
23     tree[tot]=y;
24     val[tot]=z;
25 }
26 int main()
27 {
28     scanf("%d%d%d",&n,&m,&S);
29     tot=0;
30     for (int i=1;i<=m;i++)
31     {
32         int x,y,z;
33         scanf("%d%d%d",&x,&y,&z);
34         if (x==y) continue;
35         add(x,y,z);
36     }
37     for (int i=1;i<=n;i++) 
38     {
39         visit[i]=false;
40         dis[i]=2147483647;
41     }
42     Q.push(S);
43     dis[S]=0;
44     while (!Q.empty())
45     {
46         int u=Q.top();
47         Q.pop();
48         if (visit[u]) continue;
49         visit[u]=true;
50         for (int i=head[u];i;i=Next[i])
51         {
52             int v=tree[i];
53             if (!visit[v]&&dis[v]>dis[u]+(long long)val[i])
54             {   
55                 dis[v]=dis[u]+val[i];
56                 Q.push(v);
57             }
58         }
59     }
60     for (int i=1;i<=n-1;i++) printf("%lld ",dis[i]);
61     printf("%lld\n",dis[n]);
62     return 0;
63 }