poj 3259 Wormholes (判断图是否存在负圈)
题目：http://poj.org/problem?id=3259
思路：根据BELLMAN-FORD算法，如果图中不存在从s可达的负圈，那么最短路不过经过同一个顶点两次，也就是说最多经过V-1条边，
如果存在负圈，那么这个循环更新次数会在第n次也会更新，实际上会无限更新，越来越小，所以一开始对所以点i，都把d[i]初始化为0，那么可以检查
出所有的负圈：
#include<iostream>#include<cstdlib>#include<climits>using namespace std;const int MAXN=5500;struct edge{int from,to,cost;}ed[MAXN];int n,m,w;bool solve(int e){int dis[510];for(int i=0;i<510;i++) dis[i]=0;for(int i=0;i<n;i++){for(int j=0;j<e;j++){edge es=ed[j];if(dis[es.to]>dis[es.from]+es.cost){dis[es.to]=dis[es.from]+es.cost;if(i==n-1) return 1; // 如果第n-1次还更新，那么存在负圈 }}}return 0;}int main(){int T;cin>>T;while(T--){cin>>n>>m>>w;int cnt=0;for(int i=0;i<m;i++){int x,y,z;cin>>x>>y>>z;ed[cnt].from=x;ed[cnt].to=y;ed[cnt++].cost=z;ed[cnt].from=y;ed[cnt].to=x;ed[cnt++].cost=z;}for(int i=0;i<w;i++){int x,y,z;cin>>x>>y>>z;ed[cnt].from=x;ed[cnt].to=y;ed[cnt++].cost=-z;}if(solve(cnt)) cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;}