洛谷 P3385 【模板】负环(Bellman_ford做法)

地址：https://www.luogu.com.cn/problem/P3385

 

解析：

直接Bellman_ford，然后再遍历一遍，如果还能松弛，那么就说明有负权回路。

但是题里问的是顶点1能到达的负环，所以如果有负权回路但是1不能到，依然是NO

后台是有这么个样例：

3 3

2 3  -1

3  4 -1

2   4  -1

存在负权回路但是1号点到不了，输出NO

所以再次遍历的时候，加个inf判断即可。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
const int maxn=1e4+10;
const int inf=0x3f3f3f3f;
int u[maxn],v[maxn],w[maxn];
int dis[maxn];
int n,m,tot;
void bellman_ford()
{
    memset(dis,inf,sizeof(dis));
    dis[1]=0;
    for(int k=1;k<=n-1;k++)
    {
        for(int i=1;i<=tot;i++)
        {
            dis[v[i]]=min(dis[v[i]],dis[u[i]]+w[i]);
        }
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        tot=1;
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            if(c>=0)
            {
                u[tot]=a,v[tot]=b,w[tot]=c;
                tot++;
                u[tot]=b,v[tot]=a,w[tot]=c;
                tot++;
            }
            else
            {                
                u[tot]=a,v[tot]=b,w[tot]=c;
                tot++;
            }
        }
        tot--;
        bellman_ford();
        int ok=0,ok2=0;
        for(int i=1;i<=tot;i++)
        {
            if(dis[v[i]]>dis[u[i]]+w[i]&&dis[v[i]]<inf/2)//判断1号是否能到达
            {
                ok=1;
                break;
            }
        }
        if(ok)
            cout<<"YES"<<endl;
        else    
        {
            cout<<"NO"<<endl;
        }
    }
    
}