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;
}