题目描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你判断图中是否存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

如果图中存在负权回路，则输出 Yes，否则输出 No。

数据范围

1≤n≤2000,
1≤m≤10000,
图中涉及边长绝对值均不超过 10000。

输入样例：

3 3
1 2 -1
2 3 4
3 1 -4

输出样例：

Yes

算法思路：

使用spfa算法解决是否存在负环问题：
    求负环的常用方法，基于SPFA，一般都用方法2（该题也是用方法 2）：
        方法 1：统计每个点入队的次数，如果某个点入队n次，则说明存在负环
        方法 2：统计当前每个点的最短路中所包含的边数，如果某点的最短路所包含的边数大于等于n，
                则也说明存在环

但若每次做一遍spfa()一定是正确的，但时间复杂度较高，可能会超时。
初始时将所有点插入队列中可以按如下方式理解：
    在原图的基础上新建一个虚拟源点，从该点向其他所有点连一条权值为0的有向边。
那么原图有负环等价于新图有负环。此时在新图上做spfa，将虚拟源点加入队列中。
然后进行spfa的第一次迭代，这时会将所有点的距离更新并将所有点插入队列中。

1、dist[x]：记录虚拟源点到x的最短距离

2、cnt[x] ：记录当前x点到虚拟源点最短路的边数，初始每个点到虚拟源点的距离为0，
只要他能再走n步，即cnt[x] >=n，则表示该图中一定存在负环。根据抽屉原理，从虚拟源点到x至少经过n条边时，
说明图中至少有n + 1个点，表示一定有点是重复使用；

3、若dist[j] > dist[t] + w[i],则表示从t点走到j点能够让权值变少，因此进行对该点j进行更新，
并且对应cnt[j] = cnt[t] + 1 

注意：
    该题是判断是否存在负环，并非判断是否存在从1开始的负环，因此需要将所有的点都加入队列中，
更新周围的点。

算法1

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=10010;
int n,m,x,y,z;
int dist[N];
bool st[N];
int cnt[N]; //表示当前最短路的边的数量

int h[N],w[N],e[N],ne[N],idx;
void add(int a,int b,int z)
{
    e[idx]=b;w[idx]=z;ne[idx]=h[a];h[a]=idx++;
}
int spfa()
{
    //不需要初始化:求的不是距离的最小值
    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()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>x>>y>>z;
        add(x,y,z);
    }
    if(spfa())
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

算法2