題目大意：一個農民在自家農場的不同地點發現一堆蟲洞，每個蟲洞可以回到不同長度的過去，于是這個農民想通個時間旅行回到出發點的“過去”。
構造雙向圖，實際道路為正權，時光隧道為負權，題目即為判斷有向圖負環是否存在的裸題。。。。
中途狂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}