#include<iostream>
using namespace std;
#define MAX 500
#define INF 10000000
struct Edge
{
int u,v,w;
};
Edge edge[MAX*11];
int d[MAX+1];
bool bellman_ford(int N,int EN)
{
int i,j,somethingchanged;
for(i=1;i<=N;i++)
d[i]=INF;
d[1]=0;
for(i=1;i<N;i++)
{
somethingchanged = 0;
for(j=1;j<=EN;j++)
if(d[edge[j].v]> d[edge[j].u]+edge[j].w)
{
d[edge[j].v]=d[edge[j].u]+edge[j].w;
somethingchanged=1;
}
if (!somethingchanged) break;
}
for(j=1;j<=EN;j++)
if(d[edge[j].v]> d[edge[j].u]+edge[j].w)
return true;
return false;
}
int main()
{
int F,N,M,W,EN;
int i,u,v,w;
scanf("%d",&F);
while(F--)
{
scanf("%d%d%d",&N,&M,&W);
EN=0;
for(i=1;i<=M;i++)
{
scanf("%d%d%d",&u,&v,&w);
edge[++EN].u=u;
edge[EN].v=v;
edge[EN].w=w;
edge[++EN].u=v;
edge[EN].v=u;
edge[EN].w=w;
}
for(i=1;i<=W;i++)
{
scanf("%d%d%d",&u,&v,&w);
edge[++EN].u=u;
edge[EN].v=v;
edge[EN].w=-w;
}
if(bellman_ford(N,EN)) printf("YES\n");
else printf("NO\n");
}
return 0;
}posted on 2009-07-12 11:01
wyiu 閱讀(188)
評論(0) 編輯 收藏 引用 所屬分類:
POJ