wormhole 虫洞（poj）

dfs判负权环（模板）

Description

   在一个神秘岛上，有N(1 <= N <= 500)个洞口，标号1..N，它们之间有M (1 <= M <= 2500) 条通道相连。神秘的竟然另外还有W (1 <= W <= 200)条传说中的时间虫洞----当到达通道的另一端洞口时，竟然可以比进入的时间要早！ 

   你当然想进行这样的时间之旅，希望从一个洞口s出发，经过几个通道，在比出发早些时候的时间回到洞口s。也许还能碰到自己呢,hehe,根据给定的地图，请判断能否实现这样的愿望。

Input

第一行：一个整数 F (1 <= F <= 5)，表示共有F组数据。（多组数据测试）

每组数据：第1行：三个整数 N  M  W第2至M+1行:每行三个整数 (S, E, T),表示在S与E洞口之间有一个双向通道，通过需要T(0 <= T <= 10,000) 秒。

第M+2至M+W+1行:每行三个整数 (S, E, T),表示在S与E洞口之间有一个单向通道，从S到E可以回到之前T(0 <= T <= 10,000) 秒。

Output

共1..F行，每行对应一组数据，如果可以实现愿望输出"YES",否则输出"NO".

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

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
struct tonod{
    int p,next,w;
}v[1000000],g[1000000];
queue<int> q;
int top=1,n,dis[1000000];
bool visit[1000000],bo=0;
void set()
{
    for(int i=1;i<=n;i++)
    {
        g[i].next=-1;
        dis[i]=9999999;
        visit[i]=0;
    }
    memset(v,0,sizeof(v));
    bo=0;
}
void insert(int x,int y,int k)
{
    v[top].next=g[x].next;
    v[top].p=y;
    v[top].w=k;
    g[x].next=top;
    top++;
}
void dfs(int u)
{
    visit[u]=1;
    for(int i=g[u].next;i!=-1;i=v[i].next)
    {
        int t=v[i].p,w=v[i].w;
        if(bo==1)
        return;
        if(dis[u]+w<dis[t])
        {
            dis[t]=dis[u]+w;
            if(visit[t]==0)
            {
                visit[t]=1;
                dfs(t);
            }
            else
            {
                bo=1;
                return;
            }
        }
    }
    visit[u]=0;
}
bool check()
{
    for(int i=1;i<=n;i++)
    {
        dfs(i);
        if(bo)
        return false;
    }
    return true;
}
int main()
{
    int f;
    scanf("%d",&f);
    for(int i=1;i<=f;i++)
    {
        int m,t;
        scanf("%d%d%d",&n,&m,&t);
        set();
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            insert(a,b,c);
            insert(b,a,c);
        } 
        for(int i=1;i<=t;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            c=-1*c;
            insert(a,b,c);
        }
        if(check())
        printf("NO\n");
        else
        printf("YES\n");
    }
}