题目大意：一个农民在自家农场的不同地点发现一堆虫洞，每个虫洞可以回到不同长度的过去，于是这个农民想通个时间旅行回到出发点的“过去”。
构造双向图，实际道路为正权，时光隧道为负权，题目即为判断有向图负环是否存在的裸题。。。。
中途狂RE，最后发现边数E没控制好，应为2500*2+100（有双向边）。
Bell_Ford 110ms碾过:
1
#include<cstdio>
2#include<cstdlib>
3#include<cstring>
4#define N 505
5#define E 2500*2+100 // 双向边
6#define inf 10000*2500+1
7#define MIN(a,b) (a<b)?a:b
8
struct nod
{int u,v,val;};
9struct nod edge[E];
10int n,m,w;
11int total;
12
13bool canBack(int s){
14
int i,j,k,d[N];
15 for(i=0;i<n;i++) d[i]=inf;
16 d[s]=0;
17 for(k=1;k<n;k++)
18 for(i=0;i<total;i++)
19 if( d[ edge[i].v ]>d[ edge[i].u ]+edge[i].val )
20 d[ edge[i].v ]=d[ edge[i].u ]+edge[i].val;
21
22 for(i=0;i<total;i++)
23 if( d[ edge[i].v ]>d[ edge[i].u ]+edge[i].val ) return true;
24
25 return false;
26
}
27
28int main(){
29 int t,i,j;
30 int a,b,_val;
31 scanf("%d",&t);
32
while(t--){
33 scanf("%d%d%d",&n,&m,&w);
34 total=0;
35 for(i=0;i<m;i++){
36 scanf("%d%d%d",&a,&b,&_val); --a; --b;
37 edge[total].u=a;
38 edge[total].v=b;
39 edge[total].val=_val;
40 total++;
41 edge[total].u=b;
42 edge[total].v=a;
43 edge[total].val=_val;
44 total++;
45
}
46 for(i=0;i<w;i++){
47 scanf("%d%d%d",&a,&b,&_val); --a, --b; _val*=-1;
48 edge[total].u=a;
49 edge[total].v=b;
50 edge[total].val=_val;
51 total++;
52 }
53 if( canBack(0) ) printf("YES\n");
54 else printf("NO\n");
55 }
56 return 0;
57}