模板题，只需要使用SPFA算法判断负环即可。原理是通过松弛最短路，如果图中存在负环，那这个环上的点就可以无限松弛下去，当入队次数大于 $n$ 时，就存在负环

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int mx=2e5+3;
const ll mod1=212370440130137957;
const ll mod2=(1<<30);

inline void solve()
{
    int n,m,ct=1;
    cin>>n>>m;
    vector<int>ne(m+3),e(m+3),h(m+3),w(m+3);
    auto add=[&](int d,int u,int c){
        e[ct]=u;
        w[ct]=c;
        ne[ct]=h[d];
        h[d]=ct++;
    };
    for(int i=1;i<=m;i++){
        int d,u,c;
        cin>>d>>u>>c;
        add(d,u,c);
    }

    vector<int>cnt(n+3),dis(n+3),vis(n+3);
    //入队计数，距离(默认很大)，在对内标志
    auto spfa=[&]()->bool{
        queue<int>q;
        for (int i = 1; i <= n; ++i)q.push(i),vis[i] = 1;
        //如果要加超级源点，设为n+1，q.push(st);vis[st]=1;
        //注意加边 for(int i=1;i<=n;i++)add(st,i,0);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            vis[u] = 0;
            for (int i = h[u]; i ; i = ne[i]) {
                int v = e[i];
                if (dis[v] > dis[u] + w[i]) {
                    dis[v] = dis[u] + w[i];
                    cnt[v] = cnt[u] + 1;
                    if (cnt[v] >= n) return true;
            //入队次数超过n次，即有负环
                    if (!vis[v])q.push(v),vis[v] = 1;
                }
            }
        }
        return false;
    };

    if(spfa()){
        cout<<1;
    }else{
        cout<<0;
    }
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
	return 0;
}