【题目来源】
洛谷：P5960 【模板】差分约束 - 洛谷
【题目描述】
给出一组包含 \(m\) 个不等式，有 \(n\) 个未知数的形如：
\[\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases}
\]
的不等式组，求任意一组满足这个不等式组的解。
【输入】
第一行为两个正整数 \(n,m\)，代表未知数的数量和不等式的数量。
接下来 \(m\) 行，每行包含三个整数 \(c,c',y\)，代表一个不等式 \(x_c-x_{c'}\leq y\)。
【输出】
一行，\(n\) 个数，表示 \(x_1 , x_2 \cdots x_n\) 的一组可行解，如果有多组解，请输出任意一组，无解请输出 NO。
【输入样例】
3 3
1 2 3
2 3 -2
1 3 1
【输出样例】
5 3 5
【算法标签】
《洛谷 P5960 差分约束》 #差分约束# #模板题# #Special Judge#
【代码详解】
#include <bits/stdc++.h>
using namespace std;#define int long long // 使用长整型
const int N = 5005, M = 10005; // 最大顶点数和边数
int n, m; // n: 顶点数, m: 边数
int h[N], e[M], ne[M], w[M], idx; // 链式前向星存储图
int q[N], dist[N]; // 队列和距离数组
int cnt[N], st[N]; // 松弛计数和顶点是否在队列中/*** 添加有向边* @param a 起点* @param b 终点* @param c 权重*/
void add(int a, int b, int c)
{e[idx] = b; // 边指向的顶点w[idx] = c; // 边的权重ne[idx] = h[a]; // 指向原链表头h[a] = idx++; // 更新头指针
}/*** SPFA算法求最短路径，并检测负环* @return 存在负环返回false，否则返回true*/
bool spfa()
{queue<int> q; // SPFA队列// 初始化距离为无穷大memset(dist, 0x3f, sizeof(dist));dist[0] = 0; // 超级源点距离为0q.push(0); // 超级源点入队st[0] = true; // 标记在队列中while (!q.empty()){int t = q.front(); // 取出队首q.pop();st[t] = false; // 标记不在队列中// 遍历t的所有邻接边for (int i = h[t]; i != -1; i = ne[i]){int j = e[i]; // 邻接顶点// 松弛操作：求最短路径if (dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i]; // 更新最短距离cnt[j] = cnt[t] + 1; // 松弛次数+1// 如果顶点j被松弛了n+1次，说明存在负环if (cnt[j] >= n + 1) // 注意是n+1，因为有超级源点{return false; // 存在负环}// 如果j不在队列中，入队if (!st[j]){q.push(j);st[j] = true;}}}}return true; // 不存在负环
}signed main() // 因为使用了#define int long long
{// 输入顶点数和边数cin >> n >> m;// 初始化邻接表memset(h, -1, sizeof(h));// 处理m条边while (m--){int a, b, c;cin >> a >> b >> c;// 注意：这里是 add(b, a, c)，不是常见的 add(a, b, c)add(b, a, c); // 添加有向边 b→a，权重c}// 添加超级源点到所有顶点的边for (int i = 1; i <= n; i++){add(0, i, 0); // 0→i，权重0}// 执行SPFA，检测是否存在负环if (!spfa()){puts("NO"); // 存在负环，无解}else{// 输出从超级源点到每个顶点的最短距离for (int i = 1; i <= n; i++){cout << dist[i] << " ";}cout << endl;}return 0;
}
【运行结果】
3 3
1 2 3
2 3 -2
1 3 1
0 -2 0