洛谷模板测试七倍经验：
https://www.luogu.com.cn/record/238785118
https://www.luogu.com.cn/record/238783283
https://www.luogu.com.cn/record/238788990
https://www.luogu.com.cn/record/238791631
https://www.luogu.com.cn/record/238792334
https://www.luogu.com.cn/record/238792639
https://www.luogu.com.cn/record/238794596
struct DiffConstraints {int n;std::vector<std::vector<std::array<int, 2>>> adj;std::vector<int> cnt, in, d;DiffConstraints() : n(0) {}DiffConstraints(int n_) {init(n_);}void init(int n_) {n = n_;adj.resize(n);cnt.assign(n, 0);in.assign(n, 0);d.assign(n, 0);}void add(int a, int b, int c) {adj[a].push_back({b, c});}// 添加约束 x_a - x_b <= cvoid addConstraint(int a, int b, int c) {add(b, a, c);}bool spfa(int u, int k) {std::queue<int> q;cnt.assign(n, 0);in.assign(n, 0);q.push(u);in[u] = 1;while (!q.empty()) {int u = q.front();q.pop();in[u] = 0;for (const auto& [v, w] : adj[u]) {if (d[v] < d[u] + w * k) {d[v] = d[u] + w * k;if (!in[v]) {if (++cnt[v] > n) return false;in[v] = 1;q.push(v);}}}}return true;}//求解最小值（最长路）(即spfa边权转化为负的跑最短路)bool solveMin(int u = 0) {d.assign(n, -0x3f3f3f3f);d[u] = 0;return spfa(u, -1);}//求解最大值（最短路）bool solveMax(int u = 0) {d.assign(n, 0x3f3f3f3f);d[u] = 0;return spfa(u, 1);}int dis(int x) {return d[x];}
};