点击查看代码
#include<bits/stdc++.h>
using namespace std;typedef pair<int,int> PII;
const int MAXN=1e5+10;
const int MAXM=1e6+10;
const int INF=2147483647;
struct Edge{int to;int w;int next;
}edge[MAXM];int h[MAXN];
int cnt=0;
int n,m,s;
int dist[MAXN];
bool st[MAXN];void add(int u,int v,int w)
{cnt++;edge[cnt].w=w;edge[cnt].to=v;edge[cnt].next=h[u];h[u]=cnt;
}void dijkstra()
{priority_queue<PII,vector<PII>,greater<PII>> heap;dist[s]=0;heap.push({dist[s],s});while(!heap.empty()){auto t=heap.top();heap.pop();auto ver=t.second;if(st[ver]) continue;st[ver]=true;for(int i=h[ver];i!=0;i=edge[i].next){int j=edge[i].to;if(dist[j]>dist[ver]+edge[i].w){dist[j]=dist[ver]+edge[i].w;heap.push({dist[j],j});}}}}int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n>>m>>s;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;add(u,v,w);}for(int i=1;i<=n;i++){dist[i]=INF;}dijkstra();for(int i=1;i<=n;i++){cout<<dist[i]<<" ";}return 0;}