典型的 $x_u - x_v <= y$ 形式
#include<iostream> #include<cstring> #include<queue> #define maxn 50007 using namespace std; struct edge { int to, val, nxt; }g[maxn]; int n, m, cnt, dis[maxn], hd[maxn], sum[maxn]; bool vis[maxn]; queue<int> q; void add(int u, int v, int w) { g[++cnt].val = w; g[cnt].to = v; g[cnt].nxt = hd[u]; hd[u] = cnt; } bool spfa() { memset(dis, 80, sizeof(dis)); memset(vis, 0, sizeof(vis)); dis[0] = 0, vis[0] = true; q.push(0), ++sum[0]; while (!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for (int i = hd[u]; i; i = g[i].nxt) { int v = g[i].to; if (dis[v] > dis[u] + g[i].val) { dis[v] = dis[u] + g[i].val; if (!vis[v]) { vis[v] = true; q.push(v); if (++sum[v] >= n + 1) return false; } } } } return true; } int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1, u, v, w; i <= m; i++) { cin >> u >> v >> w; add(v, u, w); } for (int i = 1; i <= n; i++) add(0, i, 0); if (spfa()) for (int i = 1; i <= n; i++) cout << dis[i] << ' '; else cout << "NO" << '\n'; return 0; }