$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

可参考： spfa判断负环

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 510, M = 5210;

int n,m1,m2;
int h[N],e[M],w[M],ne[M],idx;
int dist[N],cnt[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

bool spfa()
{
    //多组测试数据，初始化 cnt, dist, st数组
    memset(cnt,0,sizeof cnt);
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);

    //把所有点都放进去
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        q.push(i);
        st[i]=true;
    }

    while(q.size())
    {
        auto t=q.front();
        q.pop();
        st[t]=false;

        //枚举所有出边
        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];
                cnt[j]=cnt[t]+1;

                //该点到达某点走了n步
                if(cnt[j]==n) return true;

                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }

    return false;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m1>>m2;

        //多组测试数据，不要忘了初始化
        memset(h,-1,sizeof h);
        idx=0;

        //输入路径
        while(m1--)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
            add(b,a,c);
        }

        //输入虫洞
        while(m2--)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,-c);
        }

        cout<<(spfa() ? "YES" : "NO")<<endl;
    }

    return 0;
}