SPFA 就是Bellman_Ford 的优化版
思路： 任选一点u开始更新连接的v点的dist值，若能更新v点的dist，就将v点放入队列，更新从v点出发的
因为v被更新了，那么v出发的都可能被更新
直到没有一点可被更新时，算法结束
判断有无负环：
和Bellma_Ford一样，判断每个点只能最多被更新n-1次就好了(n为顶点数)
注意：此前提是不存在重边！！
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; const int INF=(1<<30); const int maxn=10000+5; struct Edge{ int to; int weight; Edge(int t,int w):to(t),weight(w){} }; vector<vector<Edge> > G(maxn); bool inq[maxn]; //判断是否在队列里 int dist[maxn]; int p[maxn]; //记录路径 int cnt[maxn]; bool Spfa(int s,int n) { memset(inq,false,sizeof(inq)); memset(cnt,0,sizeof(cnt)); memset(dist,0x7f,sizeof(dist)); queue<int> Q; dist[s]=0; inq[s]=true; Q.push(s); while(!Q.empty()) { int u=Q.front(); Q.pop(); inq[u]=false; for(int i=0;i<G[u].size();i++) { int v=G[u][i].to, w=G[u][i].weight; if(dist[v]>dist[u]+w) { dist[v]=dist[u]+w; p[v]=u; if(++cnt[v]>=n) return false; //每个点最多更新n-1次，否则存在负环; if(!inq[v]) Q.push(v),inq[v]=true; } } } return true; } int main() { int N,M,u,v,w; cin>>N>>M; while(M--) { cin>>u>>v>>w; G[u].push_back(Edge(v,w)); G[v].push_back(Edge(u,w)); } cout<<(!Spfa(1,N)?"YES":"NO")<<endl; //判断有无负环 return 0; }