Loading... emmmm。。。我不得不承认。。。学OI这么长时间，并不会写SPFA。。。 <!--more--> * * * 好吧。。直接上代码 ```cpp #include<bits/stdc++.h> using namespace std; int n,m,s,dis[10009]; bool flag,vis[10009]; int cnt[10009];//环 struct Edge{ int to,nxt,w; }e[500009]; int head[10009],tot; void add(int x,int y,int w){ e[++tot].to=y; e[tot].nxt=head[x]; e[tot].w=w; head[x]=tot; } void spfa(int st){ queue<int> q; q.push(st); dis[st]=0; while(!q.empty()){ int x=q.front(); q.pop(); vis[x]=1; for(int i=head[x];i;i=e[i].nxt){ int y=e[i].to; if(dis[y]>dis[x]+e[i].w){ dis[y]=dis[x]+e[i].w; cnt[y]++; if(cnt[y]>n){ flag=1; return; }//判环 if(!vis[y]){ q.push(y); vis[y]=1; } } } vis[x]=0; } } int main(){ cin>>n>>m>>s; for(int i=1;i<=m;i++){ int x,y,w; cin>>x>>y>>w; add(x,y,w); } memset(dis,0x3f,sizeof(dis)); spfa(s); for(int i=1;i<=n;i++){ if(dis[i]==0x3f3f3f3f) cout<<2147483647<<" "; else cout<<dis[i]<<" "; } return 0; } ``` Last modification：March 14, 2020 © Allow specification reprint Like 如果觉得我的文章对你有用，请随意赞赏