解决问题
解不等式方程。
形如\(x_i\le x_j+w\)
ps.等式可以化为两个不等式
解决方法。
相当于每条有向边松弛后的柿子。
所以跑最短路即可。
但有可能负权，而且要判无解（有负环）。
跑spfa即可
code
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m, head[N], to[N], nxt[N], len[N], ecnt, cnt[N], dis[N];
bool In_s[N];
void add_edge(int u, int v, int w) {nxt[++ecnt] = head[u]; to[ecnt] = v; len[ecnt] = w; head[u] = ecnt;}
void spfa() {
memset(dis, 0x3f, sizeof(dis));
queue<int> Q;
Q.push(0); dis[0] = 0;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
In_s[u] = 0;
for(int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if(dis[v] > dis[u] + len[i]) {
dis[v] = dis[u] + len[i];
if(!In_s[v]) {
In_s[v] = 1, Q.push(v);
if(++cnt[v] > n) {printf("NO"); exit(0);}
}
}
}
}
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {add_edge(0, i, 0);}
for(int i = 1; i <= m; i++) {
int y, x, w;
scanf("%d%d%d", &y, &x, &w);
add_edge(x, y, w);
}
spfa();
for(int i = 1; i <= n; i++) {
printf("%d ", dis[i]);
}
return 0;
}