#include <iostream>
#include <cstdio>
using namespace std;

const int INF = 100000000;
const int MAX_SIZE = 7005;
const int MAX_POINT = 502;
int n, m, w;
int dist[MAX_POINT];
int edge[MAX_SIZE][3];
int cnt;

bool relax(int u, int v, int c)
{
	if(dist[u] != INF && dist[v] > dist[u] + c)
	{
		dist[v] = dist[u] + c;
		return true;
	}
	return false;
}

bool Bellman_ford(int src)
{
	int i, j;
	bool flag;
	for(i = 1; i <= n; i++)
	{
		dist[i] = INF;
	}
	dist[src] = 0;
	////////////////////////////////////
	for(i = 1; i < n; i++)
	{
		flag = false;
		for(j = 0; j < cnt; j++)
		{
			if(relax(edge[j][0], edge[j][01], edge[j][2]))
				flag = true;
		}
		if(!flag)
			break;
	}
	for(j = 0; j < cnt; j++)
		if(relax(edge[j][0], edge[j][1], edge[j][2]))
			return false;
	return true;
}


int main()
{
	int T;
	int a, b, d;
	int i;
	cin>>T;
	while(T--)
	{
		cnt = 0;
		cin>>n>>m>>w;
		for(i = 0; i < m; i++)
		{
			cin>>a>>b>>d;
			edge[cnt][0] = a;
			edge[cnt][1] = b;
			edge[cnt++][2] = d;
			edge[cnt][0] = b;
			edge[cnt][1] = a;
			edge[cnt++][2] = d;
		}
		for(; i < m + w; i++)
		{
			cin>>a>>b>>d;
			edge[cnt][0] = a;
			edge[cnt][1] = b;
			edge[cnt++][2] = -d;
		}
		if(Bellman_ford(1))
			puts("NO");
		else
			puts("YES");
	}
	return 0;
}

• 相关文章
• 全局相关文章