#include<iostream>

using namespace std;

#define SIZE 7000
#define INF  (1<<30)

int f;
int n,m,w,edg;
struct ndoe
{
    int x;
    int y;
    int v;
}a[SIZE];
int b[SIZE];

int x,y,z;

int findMax(int a,int b)
{
    return a>b?a:b;
}
int findMin(int a,int b)
{
    return a<b?a:b;
}
bool bellman_ford(int s0)
{
    for(int i=0;n-i>0;i++) b[i]=INF;b[s0]=0;
    bool ok;
    for(int i=1;n-i>0;i++)
    {
        ok=false;
        for(int j=0;edg-j>0;j++)
        {
            if(b[a[j].x]!=INF&&b[a[j].y]>b[a[j].x]+a[j].v)
            {
                ok=true;
                b[a[j].y]=b[a[j].x]+a[j].v;
            }
        }
        if(!ok) break;
    }
    return !ok;
}    
int main()
{
    scanf("%d",&f);while(f--)
    {
        scanf("%d %d %d",&n,&m,&w);
        edg=0;
        for(int i=0;m-i>0;i++)
        {
            scanf("%d %d %d",&x,&y,&z);
            a[edg].x=x-1;
            a[edg].y=y-1;
            a[edg++].v=z;
            
            a[edg].x=y-1;
            a[edg].y=x-1;
            a[edg++].v=z;
        }
        for(int i=0;w-i>0;i++)
        {
            scanf("%d %d %d",&x,&y,&z);
            a[edg].x=x-1;
            a[edg].y=y-1;
            a[edg++].v=-z;
        }
        if(bellman_ford(0)) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

• Re:貌似不能用邻接矩阵搞，附代码 (26) hpustudent 2011-08-20 20:54:22