#include <cstdio>
#include <cstring>
#include <iostream>
using  namespace std;
int f,n,m,w;
int d[501][501];
int main()
{
    scanf("%d",&f);
    bool ans=false;
    while(f--){
        ans=false;
        int x,y,temp;
        scanf("%d %d %d",&n,&m,&w);
        for(int i=0;i<=n;i++){
            for( int j=0;j<=n;j++){
                d[i][j]=1000000;
            }
        }
        while(m--){
            scanf("%d %d %d",&x,&y,&temp);
            d[x][y]=min(d[x][y],temp);
            d[y][x]=min(d[y][x],temp);
        }
        while(w--){
            scanf("%d %d %d",&x,&y,&temp);
            temp=-temp;
            d[x][y]=min(d[x][y],temp);
        }
        for(int i=0;i<=n;i++){
            d[i][i]=0;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                for(int k=1;k<=n;k++){
                    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
                }
            }
            if(d[i][i]<0){
                ans=true;
                break;
            }
        }
        if(ans){
                cout<<"YES"<<endl;
        }
        else {
                cout<<"NO"<<endl;
        }
    }
    return 0;
}

• Re:为何floyd过不了........... (1324) Myzts 2015-09-03 10:35:42
• 时间复杂度太高了 当然过不了 (14) ploir 2017-05-04 17:43:13