Wormholes POJ - 3259 spfa判断负环

//判断负环     dist初始化为正无穷

//正环  负无穷

#include<iostream>

#include<cstring>

#include<queue>

#include<algorithm>

using namespace std;

const int N = , M = ;

int dist[N];

int h[N], e[M], w[M], ne[M], idx;

int n,m,z;

void add(int a,int b,int c)

{

    e[idx]=b;

    w[idx]=c;

    ne[idx]=h[a];

    h[a]=idx++;

}

bool st[N];

int times[N];

bool spfa()

{

    memset(st,,sizeof st);

    memset(times,,sizeof times);

    queue<int>q;

    for(int i=;i<=n;i++)

    {

        q.push(i);

        st[i]=;

        times[i]++;

    }

    while(q.size())

    {

        int t=q.front();

        q.pop();

        st[t]=;

        for(int i=h[t];~i;i=ne[i])

        {

            int j=e[i];

            if(dist[j]>dist[t]+w[i])

            {

                dist[j]=dist[t]+w[i];

                if(!st[j])

                {

                    st[j]=;

                    q.push(j);

                    times[j]++;

                    if(times[j]>n)

                        return true;

                }

            }

        }

    }

    return false;

}

int main()

{

    int t,a,b,c;

    cin>>t;

    while(t--)

    {

        cin>>n>>m>>z;

        idx=;

        memset(h,-,sizeof h);

        memset(dist,0x3f,sizeof dist);

        for(int i=;i<=m;i++)

        {

            int a,b,c;

            cin>>a>>b>>c;

            add(a,b,c);

            add(b,a,c);

        }

        for(int i=;i<=z;i++)

        {

            int a,b,c;

            cin>>a>>b>>c;

            add(a,b,-c);

        }

        if(spfa())

            cout<<"YES"<<endl;

        else

            cout<<"NO"<<endl;

    }

    return ;

}