poj3259 Wormholes(Bellman)

Description

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ’s farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.

As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .

To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

Input

Line 1: A single integer, F. F farm descriptions follow.
Line 1 of each farm: Three space-separated integers respectively: N, M, and W
Lines 2..M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.
Lines M+2..M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.

Output

Lines 1..F: For each farm, output “YES” if FJ can achieve his goal, otherwise output “NO” (do not include the quotes).

Sample Input
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8

Sample Output
NO
YES

Hint

For farm 1, FJ cannot travel back in time.
For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.

分析：
Bellman判负环
普通路是双向的
虫洞是单向的

//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

const int N=510;
int n,m,W;

struct node{
    int x,y,v;
};

struct Bellman{
    int n,m;
    vector<node> e;
    vector<int> G[N];
    bool in[N];
    int pre[N];
    int dis[N];
    int cnt[N];

    void init(int n)
    {
        this->n=n;
        e.clear();
        for (int i=1;i<=n;i++) G[i].clear();
    }

    void add(int u,int w,int z)
    {
        e.push_back((node){u,w,z});
        m=e.size();
        G[u].push_back(m-1);
    }

    bool fuhuan(int s)
    {
        memset(in,0,sizeof(in));
        memset(dis,0x33,sizeof(dis));
        memset(cnt,0,sizeof(cnt));
        queue<int> Q;
        Q.push(s);
        dis[s]=0;
        in[s]=1;

        while (!Q.empty())
        {
            int now=Q.front();
            Q.pop();
            in[now]=0;

            for (int i=0;i<G[now].size();i++)
            {
                node way=e[G[now][i]];
                int y=way.y;
                if (dis[y]>dis[now]+way.v)
                {
                    dis[y]=dis[now]+way.v;
                    if (!in[y])
                    {
                        Q.push(y);
                        in[y]=1;
                        if (++cnt[y]>n) return 1;
                    }
                }
            }
        }
        return 0;
    }
};
Bellman A;

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%d",&n,&m,&W);

        A.init(n);

        for (int i=1;i<=m;i++)
        {
            int u,w,z;
            scanf("%d%d%d",&u,&w,&z);
            A.add(u,w,z);
            A.add(w,u,z);
        }
        for (int i=1;i<=W;i++)
        {
            int u,w,z;
            scanf("%d%d%d",&u,&w,&z);
            A.add(u,w,-z);
        }

        if (A.fuhuan(1)) printf("YES
");
        else printf("NO
");
    }
    return 0;
}