就是不等式+spfa求最短路

为什么用spfa，因为这属于边问题；

这里讲一下建边；

如

1.x1-x2<3 得 x1<3+x2

2.x2-x3<-2 得x2<-2+x3

3.x1-x3<1 得 x1<x3+1

 第二种用Floyd但不建议速度慢超时

建边要建立反向边

1. 除源点外的所有顶点最短距离初始化为 ∞∞，源点 d_1d1​ 最短距离为 00。
2. 对边集 EE 进行 n-1n−1 次松弛操作。
3. 检查是否存在负权边，即是否存在未收敛的点。若存在，说明图存在负环，原不等式组无解；否则 d_idi​ 即为 x_ixi​ 的一个解。

#include <bits/stdc++.h>
using namespace std;
struct edge { 
    int u, v, w; 
} e[5050];
int d[5050], n, m, c, c1, y;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &c, &c1, &y);
        e[i].u = c1, e[i].v = c, e[i].w = y;
    } for (int i = 1; i <= n; ++i) d[i] = (i == 1 ? 0 : 0x3f3f3f3f);
	for (int i = 1; i < n; ++i) 
	    for (int j = 1; j <= m; ++j)
	        d[e[j].v] = min(d[e[j].u] + e[j].w, d[e[j].v]);
    for (int i = 1; i <= m; ++i) 
	    if (d[e[i].v] > d[e[i].u] + e[i].w) 
	        return !printf("NO");
    for (int i = 1; i <= n; ++i) printf("%d ", d[i]);
}