poj 3259 Bellman-Ford判断负权环

点击打开链接

//Bellman-Ford

#include <iostream>

#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

const int INF=1e7;

const int maxn=500+10;

struct Edge{

int from,to,weight;

Edge(int from,int to,int weight):from(from),to(to),weight(weight) {}

};

vector<Edge>edges;

int d[maxn];

int N,M,W;

bool BF()

{

    for(int i=1;i<=N;i++)

         d[i]=INF;

    d[1]=0;

    for(int k=0;k<N-1;k++)

        for(int i=0;i<edges.size();i++)

        {

            int x=edges[i].from,y=edges[i].to;

            if(d[x]<INF) d[y]=min(d[y],d[x]+edges[i].weight);

        }

    for(int i=0;i<edges.size();i++)

    {

        int x=edges[i].from,y=edges[i].to;

        if(d[y]>d[x]+edges[i].weight) return true;

    }

    return false;

}

int main()

{

    int F;

    scanf("%d",&F);

    while(F--)

    {

        scanf("%d%d%d",&N,&M,&W);

        int v1,v2,time;

        for(int i=0;i<M;i++)            //双向路径

        {

            scanf("%d%d%d",&v1,&v2,&time);

            edges.push_back(Edge(v1,v2,time));

            edges.push_back(Edge(v2,v1,time));

        }

        for(int i=0;i<W;i++)

        {

            scanf("%d%d%d",&v1,&v2,&time);

            edges.push_back(Edge(v1,v2,-time));

        }

        if(BF()) printf("YES\n");

        else printf("NO\n");

        edges.clear();

    }

    return 0;

}