模型

$n$ 元不等式， $m$ 个条件形如，

$$\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} $$

求任意解。

求解

直接把减数移过去，发现相当于松弛操作。那就转化为最短路即可。特别地，如果有负环（某值进队次数 $\ge n+1$ ）则无解。

const int N = 5e3 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int head[N], tot;
	struct Edge {
		int to, w, nxt;
	} e[N << 1];
	void add_edge(int u, int v, int w) { e[++tot] = (Edge) {v, w, head[u]}, head[u] = tot; }
	int n, m;

	int dis[N], cnt[N];
	bool vis[N];
	queue <int> q;
	bool SPFA (int s) {
		memset (dis, 0x3f3f3f3f, sizeof dis);
		dis[s] = 0;
		q.push(s);
		cnt[s] = vis[s] = 1;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			vis[u] = 0;
			for (int i = head[u]; i; i = e[i].nxt) {
				int v = e[i].to;
				if (dis[v] <= dis[u] + e[i].w) continue;
				dis[v] = dis[u] + e[i].w;
				if (!vis[v]) {
					q.push(v);
					vis[v] = 1;
					cnt[v]++;
					if (cnt[v] == n + 1) return 0;
				}
			}
		}
		return 1;
	}
	int main () {
		n = Read(), m = Read();
		for (int i = 1; i <= m; i++) {
			int u = Read(), v = Read(), w = Read();
			add_edge(v, u, w);
		}
		for (int i = 1; i <= n; i++) add_edge(n + 1, i, 0);
		if (!SPFA(n + 1)) { puts("NO"); return 0; }
		for (int i = 1; i <= n; i++) printf ("%d ", dis[i]);
		putchar(10);
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}