差分约束

差分约束用于解决如下的一些约束的可行解：

$a_1 - b_1 <= c_1\\ a_2 - b_3 <= c_2\\ \cdots\\ a_i - b_j <= c_k\\ \cdots\\$

考虑最短路的不等式
$dist[u] <= dist[v] + cost[v][u]$,
即可发现两个不等式之前形式的相似
由此我们可以将每个参数看作求最短路的图中的点
使用最短路算法得到答案

$\rm ex1$
给定$n$个变量和$m$个不等式，每个不等式形如
$x[i] - x[j] <= a[k] (0 <= i, j < n, 0 <= k < m， a[k]已知)$，求 $x[n-1] - x[0]$ 的最大值。

根据约束建图，求 $0 \rightarrow n-1$ 的最长路。