poj 3259 Wormholes 最短路

     bellman判环即可

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
Build Time:2013-05-07-22.01

*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define INF 1E9
using namespace std;
int n,m,w;
int first[505];
int U[7000];
int next[7000];
int edge[7000];
int cnt;

void build(int v,int u,int s)
{
    next[cnt]=first[v];
    first[v]=cnt;
    edge[cnt]=s;
    U[cnt]=u;
    cnt++;
}

queue<int> q;
int dis[505];
int in[505];
int bellman()
{
    bool inq[505];
    memset(inq,0,sizeof(inq));
    memset(dis,127,sizeof(dis));
    memset(in,0,sizeof(in));
    while(!q.empty())q.pop();
    q.push(1);
    in[1]=1;
    dis[1]=0;
    int v,u,i,t;
    while(!q.empty())
    {
        v=q.front();q.pop();
        inq[v]=0;
        for(i=first[v];i!=-1;i=next[i])
        {
            u=U[i];
            if(dis[u]>(t=dis[v]+edge[i]))
            {
                dis[u]=t;
                if(inq[u])continue;
                inq[u]=1;
                in[u]++;
                if(in[u]>n)return 1;
                q.push(u);
            }
        }
    }
    return 0;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(first,-1,sizeof(first));
        cnt=0;
        scanf("%d%d%d",&n,&m,&w);
        int i,u,v,s;
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&v,&u,&s);
            build(v,u,s);
            build(u,v,s);
        }
        for(i=0;i<w;i++)
        {
            scanf("%d%d%d",&v,&u,&s);
            build(v,u,-s);
        }

        if(bellman())puts("YES");
        else puts("NO");
    }
}