C++ 代码

//这道题也有收藏题解，利用抽屉原理，判断一下最短路径上是否有超过n-1
//条边，cnt[i]存i号点到源点的最短路上，边的数量。
//这道题让判断整个图中有无负环、上一题是求1到n的最短路,这道题也并不是让求从1开始的负环
//所以题解中有个思想很好，就是假设一个虚拟原点，初始把所有的点都加到队列中

/*
    多加一个0号顶点，到其他顶点的距离都是零，求0到其他顶点的最短路，如果0到i号顶点的最短路中超过了n-1个节点
    那么整个图中必定存在负环。那么本题中就必定存在负环，所以说开始把所有顶点都加入到队列中的操作，等于上述设虚拟原点
    的操作，上述虚拟原点的新图中，0到任意一个点有负环，就等于原来的图中一定存在负环，可以画个图理解一下

*/
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

const int N=100010;

int n,m;
int h[N],w[N],ne[N],e[N],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()
{
    //这里的把dist数组初始化为正无穷的操作也就不用了
    //因为我们最后注意的是cnt数组，而不是dist，dist刚开始是0的话也无所依
    //图中存在负环的话，cnt必然会>=n,相当于所有距离都减去了正无穷，但是并不
    //影响最后cnt的判断

    //更牛逼的解释来了！
    //  观察这个更新操作，if(dist[j] > dist[t] + w[i]) ) 
    //如果存在负环，则一定会更新无穷次。cnt数组肯定会>=n的 ！所以不初始化dist也没事!!
    queue<int> q;

    for(int i=1;i<=n;i++)
    {
        st[i]=true;
        q.push(i);
    }

    while(q.size())
    {
        int t=q.front();
        q.pop();

        st[t]=false;

        for(int i=h[t];i!=-1;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;

                if(cnt[j]>=n) return true;
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }

    if(spfa()) puts("Yes");
    else puts("No");
    return 0;
}