洛谷 P3385 【模板】负环

题目链接：P3385 【模板】负环

思路

       负环模版题，套一个SPFA板子，判断一下每个节点进入队列的次数，当进入队列的次数大于等于n次时，表示当前节点迭代次数超过了n - 1次，即为存在负环。

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
struct List {
  ll head[N], edge[N], next[N], dis[N], cnt, res[N];
  // 判断负环
  int count[N], flag;
  bool vis[N];
  // 处理邻接表
  void add(int x, int y, int distance) {
    next[++cnt] = head[x];
    head[x] = cnt;
    edge[cnt] = y;
    dis[cnt] = distance;
  }
  void SPFA(int start, int n) {
    memset(count, 0, sizeof count);
    memset(vis, 0, sizeof vis);
    memset(res, 0x3f, sizeof res);
    queue<int> q;
    q.push(start);
    res[start] = 0;
    vis[start] = true;
    while (!q.empty()) {
      int point = q.front();
      q.pop();
      vis[point] = false;
      for (int i = head[point]; i; i = next[i]) {
        if (res[edge[i]] > dis[i] + res[point]) {
          res[edge[i]] = dis[i] + res[point];
          count[edge[i]] = count[point] + 1;
          if (count[edge[i]] >= n) {
            cout << "YES" << endl;
            flag = 1;
            return;
          }
          if (!vis[edge[i]]) {
            q.push(edge[i]);
            vis[edge[i]] = true;
          }
        }
      }
    }
  }
  void adjacentList() {
    memset(head, 0, sizeof head);
    cnt = 0, flag = 0;
    int n, m, s;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
      ll u, v, w;
      cin >> u >> v >> w;
      add(u, v, w);
      if (w >= 0)
        add(v, u, w);
    }
    SPFA(1, n);

    if (flag == false) {
      cout << "NO" << endl;
    }
    // cout << res[n] << endl;
  }
};

int main() {
  int t;
  cin >> t;
  List list;
  while (t--) {
    list.adjacentList();
  }
  return 0;
}