YbtOj例题：最短路2 判断负环

首先，这道题的题目描述有问题！！！

“请求出图中是否存在从顶点  出发能到达的负环” 这句话是错的，事实上我们要求解的问题是“是否存在负环”

1.bfs写法

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5,M=6e3+5;
int n,m;
int dis[N];
bool vis[N];
int cnt[N];
int h[N],e[M],ne[M],w[M];
int tot;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') 
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') 
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void add(int a,int b,int c)
{
    ne[++tot]=h[a];h[a]=tot;e[tot]=b;w[tot]=c;
}
inline bool spfa()
{
    queue<int> Q;
    for(int i=1;i<=n;i++) Q.push(i),vis[i]=1;
    while(!Q.empty())
    {
        int tmp=Q.front();Q.pop();vis[tmp]=0;
        for(int i=h[tmp];i;i=ne[i])
        {
            int t=e[i];
            if(dis[t]>dis[tmp]+w[i])
            {
                dis[t]=dis[tmp]+w[i];
                cnt[t]=cnt[tmp]+1;
                if(cnt[t]>=n) return true;
                if(!vis[t]) vis[t]=1,Q.push(t);
            }
        }
    }
    return false;
}
int main()
{
    int T;
    T=read();
    while(T--)
    {
        tot=0;memset(dis,0,sizeof(dis));memset(cnt,0,sizeof(cnt));
        memset(h,0,sizeof(h));memset(vis,0,sizeof(vis));
        n=read();m=read();
        int a,b,c;
        for(int i=1;i<=m;i++) 
        {
            a=read();b=read();c=read();
            if(c>=0) add(a,b,c),add(b,a,c);
            else add(a,b,c); 
        }
        bool flag=spfa();
        if(flag) puts("YE5");
        else puts("N0");
    }
    return 0;
}

2.dfs写法

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5,M=6e3+5;
int n,m;
int dis[N];
bool vis[N];
int h[N],e[M],ne[M],w[M];
int tot;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') 
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') 
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void add(int a,int b,int c)
{
    ne[++tot]=h[a];h[a]=tot;e[tot]=b;w[tot]=c;
}
inline bool spfa(int now)
{
    vis[now]=1;
    for(int i=h[now];i;i=ne[i])
    {
        int t=e[i];
        if(dis[t]>dis[now]+w[i])
        {
            if(vis[t]) return true;
            dis[t]=dis[now]+w[i];
            if(spfa(t)) return true;
        }
    }
    vis[now]=0;
    return false;
}
int main()
{
    int T;
    T=read();
    while(T--)
    {
        tot=0;memset(dis,0,sizeof(dis));memset(h,0,sizeof(h));memset(vis,0,sizeof(vis));
        n=read();m=read();
        int a,b,c;
        for(int i=1;i<=m;i++) 
        {
            a=read();b=read();c=read();
            if(c>=0) add(a,b,c),add(b,a,c);
            else add(a,b,c); 
        }
        bool flag=false;
        for(int i=1;i<=n;i++) if(spfa(i)) 
        {
            flag=true;
            break;
        }
        if(flag) puts("YE5");
        else puts("N0");
    }
    return 0;
}