spfa AcWing 852. SPFA judgement negative ring

spfa AcWing 852. spfa Judge negative loop

Original link

AcWing 852. spfa Judge negative loop

Algorithm tags

Negative ring determination spfa

Ideas

Excerpt from the solution

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 100005;
// cnt[i] Store the i Nodes need to pass through the number of edges 
int h[N], e[N], ne[N], w[N], idx, cnt[N];
int dis[N];
bool st[N];
int n,m;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
void add(int a, int b, int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
bool sp(){
    queue<int> q;
    //  The problem is to judge whether there is a negative ring  
    //  So you need to queue all the points , Update the surrounding points 
    rep(i, 1, n+1){
        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(dis[j]>dis[t]+w[i]){
                dis[j]=dis[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;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(h, -1, sizeof h);
    n=read(), m=read();
    while(m--){
        int x=read(), y=read(), z=read();
        add(x, y, z);
    }
    if(sp()){
        puts("Yes");
    }else{
        puts("No");
    }
    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support