#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF=10000000;
int n,m,knum,id;

struct edge
{
	int v,w,nx;
}set[6005];
int head[505],Count[505],dis[505];
bool vis[505];
queue<int> Q;

void Addedge(int u,int v,int w)
{
	id++;set[id].v=v;set[id].w=w;set[id].nx=head[u];
	head[u]=id;
}

void init()
{
	int u,v,w;id=0;
	scanf("%d%d%d",&n,&m,&knum);
	memset(head,-1,sizeof(head));
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		Addedge(u,v,w);Addedge(v,u,w);
	}
	for(int i=1;i<=knum;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		Addedge(u,v,-w);
	}
}

bool spfa()
{
	memset(vis,0,sizeof(vis));
	memset(Count,0,sizeof(Count));
	for(int i=2;i<=n;i++)dis[i]=INF;
	int u,v,tmp;Q.push(1);vis[1]=1;dis[1]=0;
	while(!Q.empty())
	{
		u=Q.front();Q.pop();
		for(int k=head[u];k>0;k=set[k].nx)
		{
			v=set[k].v;
			if(dis[u]+set[k].w<dis[v])
			{
				dis[v]=dis[u]+set[k].w;
				if(!vis[v])
				{
					Q.push(v);Count[v]++;
					if(Count[v]>=n)return false;
					vis[v]=true;
				}
			}
		}
		vis[u]=false;
	}
	return true;
}

int main()
{
//	freopen("wormhole.in","r",stdin);
//	freopen("wormhole.out","w",stdout);
	int cas;
	scanf("%d",&cas);
	while(cas--)
	{
		init();
		if(spfa())puts("NO");
		else puts("YES");
	}
//	fclose(stdin); fclose(stdout);
	return 0;
}

• 注意 用数组模拟队列的朋友们 将队列改为循环队列 (89) ACAccepted 2018-12-22 19:28:09