#include<stdio.h>
#define MAX 1000000
int n;
int val[10001];
int g[5001][5001];
int Bellman()
{
	int i,j,k;
	bool flag;
//	memset(val,MAX,sizeof(val));
	for(i = 1;i <= n;i++) val[i] = MAX;
	val[1] = 0;
	for(k = 1;k < n;k++)
	{
		flag = 0;
		for(i = 1;i <= n;i++)
		{
			for(j = 1;j <= n;j++)
			{
				if(g[i][j] && val[j] > val[i] + g[i][j])
				{
					val[j] = val[i] + g[i][j];
					flag = 1;
				}
			}
		}
		if(!flag) break;
		//	return 0;
	}
//	printf("flag = %d\n",flag);
	for(i = 1;i <= n;i++)
	{
		for(j = 1;j <= n;j++)
		{
			if(g[i][j] && val[j] > val[i] + g[i][j])
				return 1;
		}
	}
	return 0;
}

int main()
{
	int i,j,t,m,w,s,e,d;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&n,&m,&w);
		for(i = 1;i <= n;i++)
			for(j = 1;j <= n;j++)
				g[i][j] = 0;
		for(i = 1;i <= m;i++)
		{
			scanf("%d%d%d",&s,&e,&d);
			g[s][e] = d;
			g[e][s] = d;
		}
		for(i = 1;i <= w;i++)
		{
			scanf("%d%d%d",&s,&e,&d);
			g[s][e] = -1*d;
		}
		if(Bellman())
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}
/*
Sample Input
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
Sample Output

NO
YES
*/

• Re:大牛帮忙看看，为什么wa呀！ (1378) suying 2009-08-06 13:03:27
• Re:大牛帮忙看看，为什么wa呀！ (68) suying 2009-08-06 13:04:20
• You bellman is WA... (0) jiang2006 2009-08-10 15:06:40