最短路

Floyd

设 f[k][x][y] 表示只经过 $1$ 到 $k$ 的情况下，$x$ 到 $y$ 的最短距离。初始化 f[0] 时，如果两个点一样，则距离为 $0$，否则为 $+\infty$。

for (k = 1; k <= n; k++) {
    for (x = 1; x <= n; x++) {
        for (y = 1; y <= n; y++) {
            f[x][y] = min(f[x][y], f[x][k] + f[k][y]);
        }
    }
}

差分约束

先从 $0$ 向每个点连一条权值为 $0$ 的边。每个条件是 $x_i-x_j⩽c$，相应地从 $j$ 向 $i$ 连一条长度为 $c$ 的有向边。跑 Bellman-Ford，则 $di{s}_i$ 就是 $i$ 可能的一个解。