#include <iostream>
#include <vector>
using namespace std;
struct Edge
{
int u,v,value;
Edge(){}
Edge( int a, int b, int c ):u(a),v(b),value(c){}
};
vector<Edge> g;
int n,m, w;
bool bellman()
{
int result[510]= { 0 };
for( int i= 0; i< n; ++i )
for( size_t j= 0; j< g.size(); j++ )
result[ g[j].v ]= min( result[ g[j].v ], result[ g[j].u ]+ g[j].value );
for( size_t i= 0; i< g.size(); ++i )
if( result[ g[i].u ]+ g[i].value< result[ g[i].v ] ) return true;
return false;
}
int main()
{
int test;
scanf("%d", &test);
while( test-- )
{
scanf("%d%d%d", &n,&m,&w);
for( int i= 0; i< m; ++i )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c );
g.push_back( Edge(a,b,c) );
g.push_back( Edge(b,a,c) );
}
for( int i= 0; i< w; ++i )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c );
g.push_back( Edge(a,b,-c) );
}
if( bellman() ) puts( "YES" );
else puts( "NO" );
g.clear();
}
return 0;
}
posted on 2008-11-07 11:36
Darren 閱讀(202)
評論(0) 編輯 收藏 引用