spfa
https://www.luogu.org/problemnew/show/P3371
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int n, m, s; 6 struct pan{ 7 int to, next, val; 8 }run[500005]; 9 int head[500005], vis[500005], dis[500005], q[500005]; 10 int node=0; 11 void add(int u,int v,int w){ 12 run[++node].to=v; 13 run[node].val=w; 14 run[node].next=head[u]; 15 head[u]=node; 16 } 17 void spfa(){ 18 int u,l=0; 19 int r=1; 20 q[1]=s; 21 vis[s]=1; 22 dis[s]=0; 23 while(l<r){ 24 u=q[++l]; 25 vis[u]=0; 26 for(int i=head[u];i!=-1;i=run[i].next){ 27 if(dis[run[i].to]>dis[u]+run[i].val){ 28 dis[run[i].to]=dis[u]+run[i].val; 29 if(vis[run[i].to]==0){ 30 vis[run[i].to]=1; 31 q[++r]=run[i].to; 32 } 33 } 34 } 35 } 36 } 37 int main(){ 38 int u,v,w; 39 cin>>n>>m>>s; 40 memset(dis,0x3f,sizeof(dis)); 41 for(int i=1;i<=m;i++){ 42 head[i]=-1; 43 } 44 for(int i=1;i<=m;i++){ 45 cin>>u>>v>>w; 46 add(u,v,w); 47 } 48 spfa(); 49 for(int i=1;i<=n;i++){ 50 if(i==s) cout<<0<<" "; 51 else{ 52 if(dis[i]==0x3f3f3f3f) cout<<2147483647<<" "; 53 else cout<<dis[i]<<" "; 54 } 55 } 56 return 0; 57 }