邻接矩阵：
Source Code

Problem: 3259		User: Belldandy
Memory: 1300K		Time: 860MS
Language: C		Result: Accepted
Source Code
#include<stdio.h>
#define INF 999999
int farm[600][600]={0};
int bellman(int n)
{
	int i=0,j=0,k=0,check[600],flag=0;
	for(i=1;i<=n;i++)
	{
		check[i]=INF;
	}
	check[1]=0;
	for(i=0;i<=n;i++)
	{
		flag=0;
		for(j=1;j<=n;j++)
		{
			for(k=1;k<=n;k++)
			{
				if(farm[j][k]+check[j]<check[k])
				{
					check[k]=check[j]+farm[j][k];
					flag=1;
				}
			}
		}
		if(!flag)
		{
			return 0;
		}
		if(i==n)
		{
			return 1;
		}
	}
}
int main()
{
	int f=0,n=0,m=0,w=0;
	int i=0,s=0,e=0,t=0,j=0;
	scanf("%d",&f);
	while(f--)
	{
		scanf("%d%d%d",&n,&m,&w);
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				farm[i][j]=INF;
			}
		}
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&s,&e,&t);
			if(farm[s][e]>t)
			{
				farm[s][e]=t;
				farm[e][s]=t;
			}
		}
		for(i=0;i<w;i++)
		{
			scanf("%d%d%d",&s,&e,&t);
			if(farm[s][e]>-t)
			{
				farm[s][e]=-t;
			}
		}
		if(bellman(n))
		{
			printf("YES\n");
		}
		else
		{
			printf("NO\n");
		}
	}
}