洛谷p4479
第一学dijkstra耶qwq
#include<bits/stdc++.h>
using namespace std;
struct edge{int to,v,next,w;
}a[500005];
struct node{int w,g;friend bool operator<(node a,node b){return a.w>b.w;}
}tmp;
int dis[100005],h[500005],b[100005];
int n,m,s,cnt;
priority_queue<node> q;
void dij(){for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f;dis[s]=0;tmp.g=s; tmp.w=0;q.push(tmp);while(!q.empty()){int u=q.top().g;q.pop();if(b[u]==1) continue;b[u]=1;for(int i=h[u];i;i=a[i].next){if(dis[a[i].to]>(long long)dis[u]+a[i].v){dis[a[i].to]=dis[u]+a[i].v;tmp.g=a[i].to; tmp.w=dis[a[i].to];q.push(tmp);} }}
}
int main(){cin>>n>>m>>s;int u,v,w;for(int i=1;i<=m;i++){cin>>u>>v>>w;a[i].to=v;a[i].v=w;a[i].next=h[u];h[u]=i; }dij();for(int i=1;i<=n;i++){cout<<dis[i]<<" ";}return 0;
}