#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iostream>
#include<cstring>
#define N 505
using namespace std;

int f,m,w,n,cnt,head[4*N],dist[N],q[N*10],num[N],map[N][N];
bool vis[N];

bool SPFA(int begin,int end)
{
	int h=-1,t=0;
	memset(vis,0,sizeof(vis));
	memset(num,0,sizeof(num));
	memset(dist,0x3f,sizeof(dist));
	q[0]=begin;vis[begin]=1;num[begin]++;
	dist[begin]=0;
	while(h<t)
	{
		int x=q[++h];
		for(int i=1;i<=n;i++)
		{
			if(dist[i]>dist[x]+map[x][i])
			{
				dist[i]=dist[x]+map[x][i];if(!vis[i])vis[i]=1,q[++t]=i,num[i]++;
			}
			if(num[i]>n)return true;
		}vis[x]=0;
	}
	return false;
}

int main()
{
	freopen("1.in","r",stdin);
	scanf("%d",&f);
	while(f--)
	{
		scanf("%d%d%d",&n,&m,&w);
		memset(map,0x3f,sizeof(map));
		for(int i=0;i<m;i++)
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			map[x][y]=map[y][x]=min(map[x][y],z);
		}
		for(int i=0;i<w;i++)
		{
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			map[x][y]=min(map[x][y],-z);
		}
		printf(SPFA(1,2)?"YES\n":"NO\n");
	}
}
一直WA。。

• Re:求教啊啊啊 (1167) Vectorxj 2016-02-28 19:49:55
• 没关联的。。。 (1198) Vectorxj 2016-02-28 19:50:17