一、差分约束
差分约束可以求解如下问题的一组解：
\[\begin{cases}x_{a_1} + c_1 \geq x_{b_1}\\ x_{a_2} + c_2 \geq x_{b_2} \\ \dots \\ x_{a_k} + c_k \geq x_{b_k}\end{cases}
\]
其中 \(1 \leq a_i, b_i \leq n\)。
我们发现这个很像求最短路的过程，即三角形不等式，所以我们从 \(a_i\) 向 \(b_i\) 连一条长度为 \(c_i\) 的边。
然后跑最短路。跑完后的 \(dis\) 数组就是一组解。
如果有负环就是无解。
因为 \(c_i\) 不一定非负，所以使用 SPFA。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
Z x = 0, f = 0;
char c = getchar ();
for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
tmp = !f ? x : -x;
}
int n, m, cnt, head[5005], dis[5005], isin[5005], que[5005];
struct Edge {
int to, nxt, dis;
} ed[10005];
inline void add_edge (int u, int v, int w) {
cnt ++;
ed[cnt] = (Edge) {v, head[u], w};
head[u] = cnt;
return ;
}
bool Memory_Ends;
signed main () {
fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
read (n), read (m);
for (int i = 1;i <= m; ++ i) {
int u, v, w;
read (u), read (v), read (w);
add_edge (v, u, w);
}
for (int i = 1;i <= n; ++ i) add_edge (0, i, 0);
for (int i = 1;i <= n; ++ i) dis[i] = 1073741819;
dis[0] = 0;
isin[0] = 1;
queue < int > q;
while (!q.empty ()) q.pop ();
q.push (0);
while (!q.empty ()) {
int u = q.front (); q.pop ();
isin[u] = 0, que[u] ++;
if (que[u] > n + 1) {
printf ("NO\n");
return 0;
}
for (int i = head[u]; i ; i = ed[i].nxt) {
int v = ed[i].to, w = ed[i].dis;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!isin[v]) isin[v] = 1, q.push (v);
}
}
}
for (int i = 1;i <= n; ++ i) printf ("%d ", dis[i]);
printf ("\n");
fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/