#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int map[2005][2005]={0};
int main()
{
	int n,m,s;
	int t;
	scanf("%d",&t);
	getchar();
	while(t--)
	{
		scanf("%d%d%d",&n,&m,&s);
//		printf("%d  %d  %d\n",n,m,s);
		for(int i=1;i<=n;i++)
		{
			map[i][i]=0;
			for(int j=1;j<=n;j++)
			{
				map[i][j]=inf;
			}
		}
		int u,v,w;
		for(int i=0;i<m;i++)
		{
			scanf("%d%d%d",&u,&v,&w);
			if(map[u][v]>w)
			map[u][v]=map[v][u]=w;
		}
		for(int i=0;i<s;i++)
		{
			scanf("%d%d%d",&u,&v,&w);
			map[u][v]=-w;
		}
		
		int flag=0;
		for(int k=1;k<=n;k++)
		{
			for(int i=1;i<=n;i++)
			{
				for(int j=1;j<=n;j++)
				{
					if(map[i][j]>map[i][k]+map[k][j])
						map[i][j]=map[i][k]+map[k][j];
				}
				if(map[i][i]<0)
				{
					flag=1;
					break;
				}
			}
			if(flag==1)
			break;
		}
		if(flag==1)
			printf("YES\n");
		else
			printf("NO\n");
	}
}

• Re:floyd 也能过 重边考虑一下 (1113) sunjianzhao 2019-09-24 22:58:43
• Re:floyd 也能过 重边考虑一下 (1113) sunjianzhao 2019-09-24 22:59:00