思路

参考文献
BFS版SPFA判负环的思路是：当路径经过节点超过n(点数)时，图存在负环。

当我们一直绕着负环走时，由负环定义，该环边权和为负数，我们走的路径权值和是越来小的。所以当图存在负环时，最短路无解(-INF)。
若一张图连通，那么它肯定是可以在经过<=n-1条边从一点到任意一点的。不存在负环时，一条路径最多经过n-1条边，；存在负环时，spfa就会一直绕着负环走，经过的边数一定超过n-1，所以只用判断最短路经过边数即可。

思考

如何用spfa求正环？

只需求最长路径，就会暴露正环

如何判断是否存在是否存在回路？

判断负环+判断正环

注意事项

不能使用Q[]数组作为队列，因为Q[]数组不会删除元素，会一直向后移动，那么空间数量级将会非常大
要用循环数组，或者<queue>

代码

#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>
#include<queue>
const int N=1e5+10;
int h[N],e[N],ne[N],w[N],idx;
int dist[N],cns[N],n,m;//cns[i]表示当前dist[i]表示的最短路径的边数
//int Q[N],front,rear;
bool st[N];
void add(int a,int b,int c){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx;
    w[idx++]=c;
}
bool spfa(){
    queue<int> Q;
    for(int i=1;i<=n;i++){//只从1开始松弛有可能到不了负环，所以每个点各自出发
        st[i]=true;
        Q.push(i);
    }
    int t,j;
    while(!Q.empty()){
        t=Q.front();
        Q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i]){
            j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                cns[j]=cns[t]+1;//1-j最短路径由1-t和t-j构成
                if(cns[j]>n-1) return true;//正常情况下1-n经过的边数最多为n-1
                if(!st[j]){
                    Q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}
int main(void){
    memset(h,-1,sizeof(h));
    cin>>n>>m;
    int a,b,c;
    for(int i=0;i<m;i++){
        cin>>a>>b>>c;
        add(a,b,c);
    }
    if(spfa()) cout<<"Yes";
    else cout<<"No";
}