前向星图+spfa
#include<bits/stdc++.h> using namespace std; int n,m; int head[200005],dist[200005],flag[200005]; int cnt=0; queue<int>q; struct Edge{ int v,next,dis; }edge[200005]; void addedge(int u,int v,int dis){ cnt++; edge[cnt].v=v; edge[cnt].dis=dis; edge[cnt].next=head[u]; head[u]=cnt; } void spfa(int t){ memset(dist,127,sizeof(dist)); memset(flag,0,sizeof(flag)); dist[t]=0; q.push(t); flag[t]=1; while(!q.empty()){ int x=q.front(); q.pop(); flag[x]=0; for(int i=head[x];i;i=edge[i].next){ if(dist[edge[i].v]>dist[x]+edge[i].dis){ dist[edge[i].v]=dist[x]+edge[i].dis; if(!flag[edge[i].v]){ q.push(edge[i].v); flag[edge[i].v]=1; } } } } for(int i=1;i<=n;i++){ if(i!=t){ cout<<dist[i]<<endl; } } } int main(){ cin>>n>>m; for(int i=0;i<m;i++){ int u,v,dis; cin>>u>>v>>dis; addedge(u,v,dis); } spfa(1); }