題目大意：一個(gè)農(nóng)民在自家農(nóng)場(chǎng)的不同地點(diǎn)發(fā)現(xiàn)一堆蟲洞，每個(gè)蟲洞可以回到不同長(zhǎng)度的過(guò)去，于是這個(gè)農(nóng)民想通個(gè)時(shí)間旅行回到出發(fā)點(diǎn)的“過(guò)去”。
構(gòu)造雙向圖，實(shí)際道路為正權(quán)，時(shí)光隧道為負(fù)權(quán)，題目即為判斷有向圖負(fù)環(huán)是否存在的裸題。。。。
中途狂RE，最后發(fā)現(xiàn)邊數(shù)E沒(méi)控制好，應(yīng)為2500*2+100（有雙向邊）。
Bell_Ford 110ms碾過(guò):
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}