http://poj.org/problem?id=3259
农夫john发现了一些虫洞，虫洞是一种在你到达虫洞之前把你送回目的地的一种方式，FJ的每个农场，由n块土地(编号为1-n),M
条路，和W个 虫洞组成，FJ想从一块土地开始，经过若干条路和虫洞，返回到他最初开始走的地方并且时间要在他离开之前，或者恰好等于他离开的时间。
把虫洞的时间看成负边权，就是判断从起点出发是否存在负权回路。那么就可以采用bellman-ford算法，注意数组开大点。
/* ***********************************************
Author : zch
Created Time :2015/5/13 19:37:22
File Name :poj - 3259 Wormholes
************************************************ */ #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
const int maxn = ;
const int maxv = ;
const int INF = <<;
struct edge{int from,to,cost;};
edge es[maxv];
int d[maxn];
int N,M,W;
int edgenum; bool short_path(int s) {
for(int i=;i<=N;i++) d[i]=INF;
d[s]=;
for(int i=;i<N;i++) {
bool flag=false;
for(int j=;j<edgenum;j++) {
edge e=es[j];
if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.cost) {
d[e.to]=d[e.from]+e.cost;
flag=true;
if(i==N-) return true; //如果 第n次仍然更新了，则存在负圈。
}
}
if(!flag) break;
}
return false;
} int main()
{
//freopen("a.txt","r",stdin);
//freopen("b.txt","w",stdout);
int F,a,b,c;
scanf("%d",&F);
while(F--) {
scanf("%d%d%d",&N,&M,&W);
edgenum=;
for(int i=;i<M;++i) { //普通路径是双向的
scanf("%d%d%d",&a,&b,&c);
es[edgenum].from=a;es[edgenum].to=b;es[edgenum++].cost=c;
es[edgenum].from=b;es[edgenum].to=a;es[edgenum++].cost=c;
}
for(int i=;i<W;++i) { //虫洞是单向的。
scanf("%d%d%d",&a,&b,&c);
es[edgenum].from=a;es[edgenum].to=b;es[edgenum++].cost=-c;
}
bool flag=short_path();
if(flag) printf("YES\n");
else printf("NO\n");
}
return ;
}