poj 3259

题意：一个图中有两种路径  1 无方向权值为政 2 有方向权值为负  问是否存在一个回路其权值为负

思路：bellman算法

#include<iostream>
using namespace std;
struct Edge
{
    int u,v;
    int w;
}e[15000];
int all;
int dist[1555];
int n,m1,m2;
bool bellman()
{
    int INF=999999999;
    int i,j;
    for(i=1;i<=n;i++)
        dist[i]=INF;
    dist[1]=0;
    for(i=1;i<=n;i++)
    {
        for(j=0;j<all;j++)
        {
            if(dist[e[j].v]>(dist[e[j].u]+e[j].w))
                dist[e[j].v]=dist[e[j].u]+e[j].w;
        }
    }
    for(j=0;j<all;j++)
    {
        if(dist[e[j].v]>(dist[e[j].u]+e[j].w))
                return true;
    }
    return false;
}
int main()
{

    int x,y,t,i;
    int cas;
    cin>>cas;
    while(cas--)
    {
        all=0;
        cin>>n>>m1>>m2;
        for(i=1;i<=m1;i++)
        {
            cin>>x>>y>>t;
            e[all].u=x;e[all].v=y;e[all].w=t;all++;
            e[all].u=y;e[all].v=x;e[all].w=t;all++;
            
        }
        for(i=1;i<=m2;i++)
        {
            cin>>x>>y>>t;
            e[all].u=x;e[all].v=y;e[all++].w=t*(-1);
        }
        if(bellman())
            cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}