Problem 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

2 3 3 1 1 2 2 1 3 4 2 3 1 3 1 3 3 2 1 1 2 3 2 3 4 3 1 8

 

Sample Output

NO YES

***************************************************************************************************************************

bellman_ford算法求负环

***************************************************************************************************************************

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6 #include
            
              7 using namespace std; 8 double dis[10001]; 9 int n,m,u,v;10 int r;11 struct edge12 {13 int u,v;14 int r;15 }e[1000001];16 int i,j,k,s;17 void bellman_ford()18 {19 //cout<<"M: "<
             
              <
              
               dis[u]+r)32 {33 dis[v]=dis[u]+r;34 flag=0;35 }36 //cout<<"dis["<
               
                <<"]: "<
                
                 <
                 
                  dis[e[it].u]+e[it].r)46 {47 puts("YES");48 return;49 }50 puts("NO");51 }52 int main()53 {54 int cas;55 scanf("%d",&cas);56 while(cas--)57 {58 k=0;59 scanf("%d%d%d",&n,&m,&s);60 for(i=1;i<=m;i++)61 {62 scanf("%d%d%d",&u,&v,&r);63 e[k].u=u;64 e[k].v=v;65 e[k++].r=r;66 e[k].u=v;67 e[k].v=u;68 e[k++].r=r;69 }70 for(i=1;i<=s;i++)71 {72 scanf("%d%d%d",&u,&v,&r);73 e[k].u=u;74 e[k].v=v;75 e[k++].r=-r;76 }77 m=k;78 bellman_ford();79 }80 return 0;81 }