1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<ext/pb_ds/priority_queue.hpp> 5 #define dis first 6 #define to second 7 #define Edge std::pair<int,int> 8 #define inf 0x7fffffff 9 #define M 50000110 #define N 1000111 int n,m,s;12 int d[N];13 struct Graph {14     std::vector<Edge> e[M];15     void add(int f,int g,int w) {16         e[f].push_back((Edge){w,g});17     }18 };19 Graph g;20 inline void dijkstra() {21     __gnu_pbds::priority_queue<Edge,std::greater<Edge> > q;22     __gnu_pbds::priority_queue<Edge,std::greater<Edge> >::point_iterator a[n+1];23     for(int i=1;i<=n;i++) if(i!=s) a[i]=q.push((Edge){d[i]=inf,i});24     a[s]=q.push((Edge){d[s]=0,s});25     while(!q.empty()) {26         Edge x=q.top();27         q.pop();28         if(x.dis==inf) continue;29         int u=x.to;30         for(std::vector<Edge>::iterator i=g.e[u].begin();i<g.e[u].end();i++) {31             Edge& e=*i;32             if(d[u]+e.dis<d[e.to]) {33                 d[e.to]=d[u]+e.dis;34                 q.modify(a[e.to],(Edge){d[e.to],e.to});35             }36         }37     }38 }39 int main() {40     scanf("%d%d%d",&n,&m,&s);41     for(int i=1;i<=m;i++) {42         int a,b,w;43         scanf("%d%d%d",&a,&b,&w);44         if(a==b) continue;45         g.add(a,b,w);46     }47     dijkstra();48     for(int i=1;i<=n;i++) {49         printf("%d ",d[i]);50     }51     printf("\n");52     return 0;53 }