最短路+判负环
优点：
1.判负环比较稳（相对于spfa+dfs/bfs)
2.存图超简单
3.Bellman-Ford枚举的是边集{E}，不需要考虑不联通的区块；如果写Dijkstra或SPFA，则要考虑这种情况。
缺点：专求最短路复杂度大了点O(n*m)
分3个部分：
1.做n-1次循环
2.每个循环中遍历所有的m条边，进行松弛。(若要记录最短路线在这里做文章，打个pre数组）
3.算完上面最短路后再枚举一次所有的m条边，若还可以继续松弛的话，说明存在负环
struct edge{
int u,v,w;
}e[N<<1];
int inf=0x7fffffff;
me(dis,inf);
dis[1]=0;
一般板子：
For(i,1,n-1) For(j,1,m) if(dis[e[j].u]+e[j].w<dis[e[j].v]){ dis[e[j].v]=dis[e[j].u]+e[j].w; pre[e[j].v]=e[j].u;//打印路线 } For(j,1,m) if(dis[e[j].u]+e[j].w<dis[e[j].v]){ flag=0; break; } if(flag)cout<<"负环"; else cout<<dis[n];
专门处理负环的板子：
bool bellman_ford(int s){ bool update=false; For(i,1,n-1) For(j,1,m){ int u=e[j].u,v=e[j].v,w=e[j].w; if(dis[u]!=inf&&dis[u]+w<dis[v]){ dis[v]=dis[u]+w; update=true; } if(!update)return false; //如果已经更新完毕了那就可以提前跳出 } For(j,1,m){ int u=e[j].u,v=e[j].v,w=e[j].w; if(dia[u]!=inf&&dis[u]+w<dis[v])return true; } return false; }
原文：https://www.cnblogs.com/planche/p/9388227.html