SPFA

const int inf = 1e9;
struct Graph {
  int n;
  vector<vector<pair<int, int>>> adj;
  Graph(int n_) {
    n = n_;
    adj.resize(n + 1, {});
  }
  bool spfa(int s) {
    vector<int> d(n + 1, inf), vis(n + 1), cnt(n + 1);
    queue<int> q;
    q.emplace(s);
    vis[s] = 1;
    d[s] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      vis[u] = false;
      for (auto [v, w] : adj[u]) {
        if (d[v] > d[u] + w) {
          d[v] = d[u] + w;
          cnt[v] = cnt[u] + 1;
          if (cnt[v] >= n + 10) { // 一定是>=总点数！
            return false;
          }
          if (!vis[v]) {
            q.emplace(v);
            vis[v] = true;
          }
        }
      }
    }
    return true;
  }
  void addEdge(int u, int v, int w) {
    adj[u].emplace_back(v, w);
  }
};