poj3259 bellman水题

poj3259http://poj.org/problem?id=3259
最简单的bellman，判断是否有负环，n-1次松弛后若还能松弛，则有负环

#include <iostream>
#include <fstream>
#define INF 999999999
using namespace std;

struct E
{
	int u;
	int v;
	int w;
}edges[6000];

int n,m,w;
int countEdge;
int dist[1000];



void addEdge(int e,int s,int t)
{
	countEdge++;
	edges[countEdge].u=e;
	edges[countEdge].v=s;
	edges[countEdge].w=t;
	
	
}

bool bellman()
{
	int i,j;
	dist[1]=0;
	for(i=2;i<=n;i++)
		dist[i]=INF;
	for(i=1;i<n;i++)
		for(j=1;j<=countEdge;j++)
		{
			if(dist[edges[j].v]>dist[edges[j].u]+edges[j].w)
				dist[edges[j].v]=dist[edges[j].u]+edges[j].w;
		}
	for(i=1;i<countEdge;i++)
	{
		if(dist[edges[i].v]>dist[edges[i].u]+edges[i].w)
			return true;
	}
	return false;
	
}

int main()
{
	int f;
//	ifstream cin("1.txt");
	cin>>f;
	while(f--)
	{
		cin>>n>>m>>w;
		countEdge=0;
		int i,s,e,t;
		for(i=0;i<m;i++)
		{
			cin>>s>>e>>t;
			addEdge(s,e,t);
			addEdge(e,s,t);
		}
		for(i=0;i<w;i++)
		{
			cin>>s>>e>>t;

			addEdge(s,e,-t);
		}
		if(bellman())
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
		
	}

	
	return 0;
}