Wormholes

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 36860		Accepted: 13505

Description

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.

As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .

To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

Input

Line 1: A single integer, 

F. 

F farm descriptions follow. 

Line 1 of each farm: Three space-separated integers respectively: 

N, 

M, and 

W 

Lines 2..

M+1 of each farm: Three space-separated numbers (

S, 

E, 

T) that describe, respectively: a bidirectional path between 

S and 

E that requires 

T seconds to traverse. Two fields might be connected by more than one path. 

Lines 

M+2..

M+

W+1 of each farm: Three space-separated numbers (

S, 

E, 

T) that describe, respectively: A one way path from 

S to 

E that also moves the traveler back 

T seconds.

Output

Lines 1..

F: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).

Sample Input

23 3 11 2 21 3 42 3 13 1 33 2 11 2 32 3 43 1 8

Sample Output

NOYES 题解： 这道题意思是这个人的农田里有道路，还有虫洞，道路是双向的，虫洞单向，他喜欢虫洞旅行，想要从起点再回到起点时间在出发的时间之前，经过虫洞时间倒退； 做这道题其实就是判断最短路有没有负环的问题；因为只要有负环，就会无限循环，到起点自然就时间倒退了； 代码：SPFA

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int INF=0x3f3f3f3f; 6 const int MAXN=510; 7 const int MAXM=10010*2; 8 int dis[MAXN],vis[MAXN],used[MAXN],head[MAXM]; 9 int N,W,M,en,flot;10 queue
        
         dl;11 struct Edge{12     int from,to,value,next;13 };14 Edge edg[MAXM];15 void initial(){16     memset(dis,INF,sizeof(dis));17     memset(vis,0,sizeof(vis));18     memset(used,0,sizeof(used));19     memset(head,-1,sizeof(head));20     while(!dl.empty())dl.pop();21     en=0;flot=0;22 }23 void print(){24     if(flot)puts("YES");25     else puts("NO");26 }27 void add(int u,int v,int w){28     Edge E={u,v,w,head[u]};29     edg[en]=E;30     head[u]=en++;31 }32 void SPFA(int sx){33     dis[sx]=0;vis[sx]=1;dl.push(sx);34     used[sx]++;35     while(!dl.empty()){36         int k=dl.front();37         dl.pop();38         vis[k]=0;39         if(used[k]>N){40             flot=1;41             break;42                 }43         for(int i=head[k];i!=-1;i=edg[i].next){44             int v=edg[i].to;45             if(dis[k]+edg[i].value
         
          N){52                         flot=1;return ;53                     }54                 }55             }56         }57     }58 }59 void get(){60     int F,a,b,c;61     scanf("%d",&F);62     while(F--){63         initial();64         scanf("%d%d%d",&N,&M,&W);65         while(M--){66             scanf("%d%d%d",&a,&b,&c);67             add(a,b,c);68             add(b,a,c);69         }70         while(W--){71             scanf("%d%d%d",&a,&b,&c);72             add(a,b,-c);73         }74         SPFA(1);75         print();76     }77 }78 int main(){79     get();80     return 0;81 }
         
        
       
      
     

 Bellman:

1 #include
     
       2 #include
      
        3 const int INF=0x3f3f3f3f; 4 const int MAXN=510; 5 const int MAXM=6000; 6 int dis[MAXN]; 7 struct Edge{ 8     int u,v,w; 9 };10 Edge edg[MAXM];11 int N,M,W,top;12 bool Bellman(int sx){13     int u,v,w;14     memset(dis,INF,sizeof(dis));15     dis[sx]=0;16     for(int i=1;i<=N;i++){17         for(int j=0;j