4640031_ac_266ms_308k.cpp

部分PKU上的源码

#include<iostream>
#define MAX 100000
using namespace std;
struct path
{
	int u;
	int v;
	int w;
}e[27000];
int el;
int d[505];
int n,M,W;
void bellman()
{
	int f;
	for(int i=0;i<n-1;i++)
	{
		f=0;
		for(int j=0;j<el;j++)
		{
			if(d[e[j].v]>d[e[j].u]+e[j].w)
			{
				d[e[j].v]=d[e[j].u]+e[j].w;
				f=1;
			}
		}
		if(!f) {cout<<"NO"<<endl;return;}
	}
	for(int k=0;k<el;k++)
	{
		if(d[e[k].v]>d[e[k].u]+e[k].w) {cout<<"YES"<<endl;return;}
	}
	cout<<"NO"<<endl;
}
int main()
{
	int testnumber=0;
	cin>>testnumber;
	for(int count=1;count<=testnumber;count++)
	{
		el=0;
		cin>>n>>M>>W;
		int t1,t2,t3;
		int count2;
		for(count2=1;count2<=M;count2++)
		{	
			cin>>t1>>t2>>t3;
			e[el].u=t1;
			e[el].v=t2;
			e[el++].w=t3;
			e[el].u=t2;
			e[el].v=t1;
			e[el++].w=t3;
		}
		for(count2=1;count2<=W;count2++)
		{
			cin>>t1>>t2>>t3;
			//t3*=-1;
			e[el].u=t1;
			e[el].v=t2;
			e[el++].w=-t3;
		}
		bellman();
	}
	return 0;
}