poj 3259 Wormholes(bellman-ford)

http://blog.csdn.net/yslcl12345/article/details/50573269

這個題解是用floyd做的，翻譯題目翻譯的挺好

#include <cstdio>
const int INF = ;
struct node
{
    int u,v,w;
};

node edges[];
int dis[];
int index;
int N,M,W;

bool bellmanFord()
{
    for(int i = ; i <= N; ++i)
        dis[i] = INF;
    dis[] = ;
    for(int i = ; i < N; ++i)
    {
        for(int j = ; j < index; ++j)
        {
            if(dis[edges[j].v] > dis[edges[j].u] + edges[j].w)
            {
                dis[edges[j].v] = dis[edges[j].u] + edges[j].w;
                if(i == N-) return true;
            }
        }
    }
    return false;
}

int main()
{
    int t;
    int a,b,c;
    scanf("%d",&t);
    while(t--)
    {
        index = ;
        scanf("%d %d %d",&N,&M,&W);
        for(int i = ; i < M; ++i)
        {
            scanf("%d %d %d",&a,&b,&c);
            edges[index].u = a;
            edges[index].v = b;
            edges[index++].w = c;

            edges[index].u = b;
            edges[index].v = a;
            edges[index++].w = c;
        }
        for(int i = ; i < W; ++i)
        {
            scanf("%d %d %d",&a,&b,&c);
            edges[index].u = a;
            edges[index].v = b;
            edges[index++].w = -c;
        }
        if(bellmanFord())
            printf("YES\n");
        else
            printf("NO\n");
    }
    return ;
}