[NFLS 1451/3] 有向图++ 题解

大意

在有向图上, 有长度为 $x$ 的边, 对于每个询问，给定 $s, t$, 求出当 $x$ 取不同正整数时, 最短路的值有多少种, 并且求出他们的和.

题解

对原图跑分层图最短路, 记 $dis_{u, i}$ 为从 $s$ 至 $u$ , 恰好经过 $i$ 条长度为 $x$ 的边的最短路, 在求最短路时, 令 $x \leftarrow 0$.

可以得到若干条方程 $y_u = ix + dis_{t, i}$, 枚举考虑最短路经过 $i$ 条长度为 $x$ 的边的情况, 联立所有方程, 可以得到 (设 $f_i = dis_{u, i}$)

$$x \lt \frac {f_j - f_i} {i - j}, i > j \newline x \ge \frac {f_j - f_i} {i - j}, j < i \newline$$

然后可以求出 $x$ 的取值范围, 对答案的贡献即为

$$cnt \leftarrow cnt + hi_i - lo_i + 1 \newline$$

$$res \leftarrow res + i \frac {(hi_i + lo_i)(hi_i - lo_i +1)} 2 + dis_{t, i}(hi_i - lo_i + 1) \newline$$

(注: 不等式中, 不能两边都取等, 否则整数值会被重复考虑. )