spfa 判断负环 – 算法板子

#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int h[N], ne[N], v[N], e[N], idx; int cnt[N], d[N]; bool vis[N]; int n, m; void add(int x, int y, int z) {   v[++idx] = y;   e[idx] = z;   ne[idx] = h[x];   h[x] = idx; };  bool spfa() {     queue<int> q;     for (int i = 1; i <= n; ++i) {         q.push(i);         vis[i] = 1;     }     while (!q.empty()) {         int f = q.front();         q.pop();         vis[f] = 0;         for (int idx = h[f]; idx != -1; idx = ne[idx]) {             int t = v[idx], w = e[idx];             if (d[t] > d[f] + w) {                 d[t] = d[f] + w;                 cnt[t] = cnt[f] + 1;                 if (cnt[t] >= n) return true;                 if (!vis[t]) {                     vis[t] = 1;                     q.push(t);                 }             }         }     }     return false; };  int main() {     memset(h, -1, sizeof h);     cin >> n >> m;     for (int i = 1; i <= m; ++i) {         int x, y, z;         scanf("%d%d%d", &x, &y, &z);         add(x, y, z);     }          if (spfa()) {         puts("Yes");     } else {         puts("No");     }          return 0; };

spfa 判断负环 – 算法板子leetcode刷题题解部分资料来自网络,侵权毕设源码联系删除

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » spfa 判断负环 – 算法板子leetcode刷题题解