#include <iostream>
using namespace std;

#define MAXN 501
#define inf 1000000000
typedef int elem_t;

int bellman_ford(int n, elem_t mat[][MAXN], int s, elem_t min[MAXN], int pre[MAXN])
{
	int v[MAXN], i, j, k, tag;
	for (i = 0; i < n; i++)
		min[i] = inf, v[i] = 0, pre[i] = -1;
	for (min[s] = 0, j = 0; j < n; j++)
	{
		for (k = -1, i = 0; i < n; i++)
			if (!v[i] && (k == -1 || min[i] < min[k]))
				k = i;
		for (v[k] = 1, i = 0; i < n; i++)
			if (!v[i] && mat[k][i] >= 0 && min[k] + mat[k][i] < min[i])
				min[i] = min[k] + mat[pre[i] = k][i];
	}
	for (tag = 1, j = 0; tag && j <= n; j++)
		for (tag = i = 0; i < n; i++)
			for (k = 0; k < n; k++)
				if (min[k] + mat[k][i] < min[i])
					min[i] = min[k] + mat[pre[i] = k][i], tag = 1;
	return j <= n;
}
int main()
{
	int map[MAXN][MAXN];
	int n;
	int min[MAXN];
	int pre[MAXN];
	int i, j;
	int n1,m1,w1,s,e,t;
	cin >> n;
	for(i = 0 ;i < n ;i ++)
	{
                memset(map,0,sizeof(map));
		cin>>n1>>m1>>w1;
		for(j = 0; j < m1; j++)
		{
			cin>>s>>e>>t;
			map[s-1][e-1] = t;
		}
		for(j = 0; j < w1; j++)
		{
			cin>>s>>e>>t;
			map[s-1][e-1] = -t;
		}
		bool con = false;
		for(j = 0 ;j < n1 ;j ++)
		{
			if(!bellman_ford(n1, map, j, min, pre))
			{
				cout<<"YES"<<endl;
				con = true;
				break;
			}
		}
		if(!con)
		{
			cout<<"NO"<<endl;
		}
	}
	return 0;
}
//测试数据没问题啊。。。

• Re:为什么会WA?会的人帮我看看吧，不胜感激！ (15) yangkeao 2016-07-30 14:58:27