#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> typedef long long LL; using namespace std; LL RD(){ LL out = 0,flag = 1;char c = getchar(); while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();} while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();} return flag * out; } const LL maxn = 1000019,INF = 0xfffffffffffffff; LL head[maxn],nume = 1; struct Node{ LL v,dis,nxt; }E[maxn << 3]; void add(LL u,LL v,LL dis){ E[++nume].nxt = head[u]; E[nume].v = v; E[nume].dis = dis; head[u] = nume; } LL num, nr, s; bool vis[maxn]; LL d[maxn]; struct node{ LL u, d; bool operator < (const node &a)const{ return d > a.d; } }; void Djs(LL s){ for(LL i = 1;i <= num;i++)d[i] = INF; priority_queue<node>Q; d[s] = 0; Q.push((node){s, d[s]}); while(!Q.empty()){ LL u = Q.top().u;Q.pop(); if(vis[u])continue; vis[u] = 1; for(LL i = head[u];i;i = E[i].nxt){ LL v = E[i].v, dis = E[i].dis; if(d[u] + dis < d[v]){ d[v] = d[u] + dis; Q.push((node){v, d[v]}); } } } } int main(){ num = RD();nr = RD();s = RD(); for(int i = 1;i <= nr;i++){ LL u = RD(), v = RD(), dis = RD(); add(u, v, dis); } Djs(s); for(int i = 1;i <= num;i++)printf("%lld ", d[i]); return 0;
}
1 #include<bits/stdc++.h> 2 using namespace std; 3 struct SYM{ 4 int to,next,w; 5 }edge[500010]; 6 struct LKJ{ 7 int v,c; 8 bool operator <(const LKJ &a)const { 9 return c>a.c; 10 } 11 }; 12 priority_queue<LKJ,vector<LKJ> > q; 13 int head[101000],vis[101000],tot,dis[101000],n,m,k; 14 void add(int x,int y,int w){ 15 edge[++tot].to=y; 16 edge[tot].w=w; 17 edge[tot].next=head[x]; 18 head[x]=tot; 19 } 20 void dij(int s){ 21 dis[s]=0; 22 LKJ hh;hh.v=s;hh.c=0; 23 q.push(hh); 24 while(!q.empty()){ 25 LKJ tmp=q.top();q.pop(); 26 int x=tmp.v; 27 if(vis[x]) continue;vis[x]=1; 28 for(int i=head[x];i;i=edge[i].next) 29 if(!vis[edge[i].to]&&dis[edge[i].to]>dis[x]+edge[i].w){ 30 dis[edge[i].to]=dis[x]+edge[i].w; 31 hh.v=edge[i].to;hh.c=dis[edge[i].to]; 32 q.push(hh); 33 } 34 } 35 } 36 int main(){ 37 memset(dis,127,sizeof(dis)); 38 int x,y,w; 39 scanf("%d%d%d",&n,&m,&k); 40 for(int i=1;i<=m;i++){ 41 scanf("%d%d%d",&x,&y,&w); 42 add(x,y,w); 43 } 44 dij(k); 45 for(int i=1;i<=n;i++){ 46 if(dis[i]==2139062143) printf("2147483647 "); 47 else printf("%d ",dis[i]); 48 } 49 return 0; 50 }