测试点信息源代码 源代码 复制 //#pragma G++ diagnostic error "-std=c++11" //#pragma GCC diagnostic error "-std=c++11" #include<bits/stdc++.h> #define int long long #define ORZ 2147483647 using namespace std; const int N=1e7+17; int n,m,s,id,to[N],ne[N],head[N],w[N]; void add(int x,int y,int z) { id++; w[id]=z; to[id]=y; ne[id]=head[x]; head[x]=id; } struct node { int num,id; bool operator <(const node&a)const { return num>a.num; } }; int dis[N],vis[N]; void dijkstra() { for(int i=1;i<=n;i++) { dis[i]=ORZ; } memset(vis,0,sizeof vis); priority_queue<node>p; dis[s]=0; p.push((node){0,s}); while(!p.empty()) { node t=p.top(); p.pop(); if(vis[t.id]||t.num!=dis[t.id]) { continue; } int idx=t.id; vis[idx]=1; for(int j=head[idx];j;j=ne[j]) { int v=to[j]; if(!vis[v]&&dis[v]>t.num+w[j]) { dis[v]=t.num+w[j]; p.push((node){dis[v],v}); } } } } signed main() { cin>>n>>m>>s; for(int i=1,r1,r2,r3;i<=m;i++) { cin>>r1>>r2>>r3; add(r1,r2,r3); } dijkstra(); for(int i=1;i<=n;i++) { cout<<dis[i]<<' '; } return 0; }