poj-3259-Wormholes


前のテーマと同じように、負の回路があるかどうかを求めています.同じようにBellman-fordアルゴリズムを使って、前の問題と差が少ないので、習ったばかりのアルゴリズムを固めましょう.
#include<stdio.h>
#define max 1000000
int step;
int n,m,w;
struct list
{
	int a;
	int b;
	int v;
}map[6000];
int bf()
{
	int i,j,d[6000];
	for(i=1;i<step;i++)
	{
		d[i]=max;
	}
	d[1]=0;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<step;j++)
		{
			if(d[map[j].a]!=max&&(d[map[j].b]>(d[map[j].a]+map[j].v)))
			{
				d[map[j].b]=(d[map[j].a]+map[j].v);
			}
		}
	}
	for(j=1;j<step;j++)
	{
		if(d[map[j].b]>(d[map[j].a]+map[j].v))
			return 1;
	}
	return 0;
}
int main()
{
	int T,i,s,e,t;
	scanf("%d",&T);
	while(T--)
	{
		step=1;
		scanf("%d%d%d",&n,&m,&w);
		for(i=2;i<=m+1;i++)
		{
			scanf("%d%d%d",&s,&e,&t);
			map[step].a=s;
			map[step].b=e;
			map[step].v=t;
			step++;
			map[step].a=e;
			map[step].b=s;
			map[step].v=t;
			step++;
		}
		for(i=m+2;i<=m+w+1;i++)
		{
			scanf("%d%d%d",&s,&e,&t);
			map[step].a=s;
			map[step].b=e;
			map[step].v=-t;
			step++;
		}
		if(bf())
		printf("YES
"); else printf("NO
"); } return 0; }