poj3259 Wormholes

用bellman_ford判断图中有无负环。可假设存在某一源点到各点距离为0，即初始化数组value为零。

数据里边的数貌似不止2500，最开始数组开小了结果RE。

#include<iostream>
#include<stdio.h>
#include<string.h>
#define MAXD 510
using namespace std;
int F,N,M,W,S,E,T;
struct NODE
{
    int v1;
    int v2;
    int d; //d为边权值
}node[10*MAXD]; //用node记录边

int bellman_ford()
{
    int value[N+1];
    memset(value,0,sizeof(value));
    int i,j;
    int t=N;
    int u,v,d;
    while(t--)
    {
        for(i=0;i<(2*M+W);i++)
        {
            u=node[i].v1;
            v=node[i].v2;
            d=node[i].d;
            if(value[v]>value[u]+d)
            value[v]=value[u]+d;
        }
    }
    for(i=0;i<(2*M+W);i++)
    {
        u=node[i].v1;
        v=node[i].v2;
        d=node[i].d;
        if(value[v]>value[u]+d)
        return 0;
    }
    return 1;
}
int main()
{
    //freopen("test.txt","r",stdin);
    scanf("%d",&F);
    while(F--)
    {
        scanf("%d%d%d",&N,&M,&W);
        int i,j=0; //j用来记录第几条边
        for(i=0;i<M;i++)
        {
            scanf("%d%d%d",&S,&E,&T);
            node[j].v1=S;
            node[j].v2=E;
            node[j].d=T;
            j++;
            node[j].v1=E;
            node[j].v2=S;
            node[j].d=T;
            j++;
        }
        for(i=0;i<W;i++)
        {
            scanf("%d%d%d",&S,&E,&T);
            node[j].v1=S;
            node[j].v2=E;
            node[j].d=(-1)*T;
            j++;
        }
        int ans;
        ans=bellman_ford();
        if(!ans)
        printf("YES\n");
        else
        printf("NO\n");
    }
}