【原创】
题目大意
John有N个农场，一共有M条边，在农场上出现了W个虫洞(W是一条边)，其中M是双向普通边，W是单向虫洞边。John穿行于农场之间每经过一条边(S到E)的时间为+T，每经过虫洞会时间倒流，经过-T。问John会不会在某一刻看到以前的自己。这个题目即问的是，存不存在负权环。bollman_ford
先粘一下百度百科的话：
Bellman - ford算法是求含负权图的单源最短路径算法，效率很低，但代码很容易写。其原理为持续地进行松弛（原文是这么写的，为什么要叫松弛，争议很大），在每次松弛时把每条边都更新一下，若在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。Bellman - ford算法有一个小优化：每次松弛先设一个标识flag，初值为FALSE，若有边更新则赋值为TRUE，最终如果还是FALSE则直接成功退出。Bellman-ford算法浪费了许多时间去做没有必要的松弛，而SPFA算法用队列进行了优化，效果十分显著，高效难以想象。SPFA还有SLF，LLL，滚动数组等优化。
首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。
在对每条边进行第1遍松弛的时候，生成了从s出发，层次至多为1的那些树枝。也就是说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边进行第2遍松弛的时候，生成了第2层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路径……。因为最短路径最多只包含|v|-1 条边，所以，只需要循环|v|-1 次。
每实施一次松弛操作，最短路径树上就会有一层顶点达到其最短距离，此后这层顶点的最短距离值就会一直保持不变，不再受后续松弛操作的影响。（但是，每次还要判断松弛，这里浪费了大量的时间，怎么优化？单纯的优化是否可行？）
注意：上述只对正权图有效。如果存在负权不一定第i次就能确定最短路，且与边的顺序有关。
如果没有负权回路，由于最短路径树的高度最多只能是|v|-1，所以最多经过|v|-1遍松弛操作后，所有从s可达的顶点必将求出最短距离。如果 d[v]仍保持 +∞，则表明从s到v不可达。
如果有负权回路，那么第 |v| 遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。
这其他的不多说，先说一下松弛计算，其实就是更新距离嘛，这种思想在运筹学好像称之为松弛，我们知道，假如图中的边全部为正权边就一定会有最短路径，假如存在负权环，那么每走一圈，起点的权值就会比原来小，那么你走无数圈，你的权值就会无限减小。那么百度百科的意思就是，你先做标准次数的距离更新(理论上讲已经无法再更新了)，假如你再一次更新距离，如果还能更新，就一定存在负权环咯。
/*题目大意
John有N个农场，一共有M条边，在农场上出现了W个虫洞(W是一条边)，其中M是双向普通边
，W是单向虫洞边。John穿行于农场之间每经过一条边(S到E)的时间为+T，每经过虫洞会时
间倒流，经过-T。问John会不会在某一刻看到以前的自己。
这个题目即问的是，存不存在负权环。bollman_ford
*/ #include<cstdio>
#include<iostream>
#include<memory.h>
#define max 9999999
using namespace std;
int n,m,w,top;
typedef struct
{
int x,y,t;
} e;
e edge[]; bool bellman_ford(int en)//en = top-1,即边的数量
{
int dis[],u,v,w;
for(int i=;i<=n;i++) dis[i] = max;
dis[] = ;
for(int i=;i<n-;i++) //百科说:首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。
{
//for(int k=1;k<=n;k++) printf("%d ",dis[k]);
for(int j = ;j <= en;j++)
{
u = edge[j].x;
v = edge[j].y;
w = edge[j].t;
if(dis[u]<max && dis[u]+w < dis[v])
{
dis[v] = dis[u]+w;
}
}
}
for(int i=;i<=en;i++)
{
u = edge[i].x;
v = edge[i].y;
w = edge[i].t;
if(dis[u]<max && dis[u]+w<dis[v])
{
return true;//极限更新n-1，我们再更新en次，如果还能再更新，那返回TRUE表示存在负权环
}
}
return false;//不能再更新了，返回FALSE
}
int main(){
int T;
scanf("%d", &T);
while(T--){
top = ;
scanf("%d %d %d", &n, &m, &w);
for(int i=; i<m; i++){
int a,b,c;
scanf("%d %d %d", &a, &b, &c);
edge[top].x = a;
edge[top].y = b;
edge[top].t = c;
top++;
edge[top].x = b; //这里一定要注意，普通的边是双向的，所以要重新反过来存一次
edge[top].y = a;
edge[top].t = c;
top++;
}
for(int i=; i<w; i++){
int a,b,c;
scanf("%d %d %d", &a, &b, &c);
edge[top].x = a;
edge[top].y = b;
edge[top].t = -c; //虫洞是负的且是单向所以 取负 只用存一次
top++;
}
if(bellman_ford(top-)) printf("YES\n");
else printf("NO\n");
}
}