SPFA判断负环
基本过程与spfa求最短路相同，但是额外记录一个 cnt数组，表示到当前点的最短路经过的边的条数，如果cnt[i]>=n说明一定存在一个负环。
此外，初始化队列的时候，要将所有点都加入队列，因为1可能到不了负环存在的位置。
#include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) #define debug(x,y) cerr << (x) << " == " << (y) << endl; using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } //template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 1e5 + 10; int n, m; vector<PII>vec[N]; int d[N], cnt[N]; bool vis[N]; bool spfa() { queue<int>q; memset(d, 0x3f, sizeof d); d[1] = 0; vis[1] = true; for (int i = 1; i <= n; ++i)q.push(i); while (q.size()) { int t = q.front(); q.pop(); vis[t] = false; for (int i = 0; i < vec[t].size(); ++i) { int j = vec[t][i].second; int dis = vec[t][i].first; if (d[j] > d[t] + dis) { d[j] = d[t] + dis; if (!vis[j])q.push(j); cnt[j] = cnt[t] + 1; if (cnt[j] >= n)return true; } } } return false; } void solve() { cin >> n >> m; while (m--) { int u, v, w; scanf("%d%d%d", &u, &v, &w); vec[u].push_back({ w,v }); } if (spfa())puts("Yes"); else puts("No"); } signed main() { // int _; cin >> _; // while (_--) solve(); return 0; }
