Difference Constraints

差分约束是用来解形如 \(x_{1}-x_{2}\leqslant k\) 的若干个方程的算法。

另外，如果有负环则无解。

时间复杂度 \(\Theta(\rm SPFA)\)。

需要注意的是，最短路求的是以起始点为基准的最大解，而最长路求的是以起始点为基准的最小解。