P6573 [BalticOI 2017] Toll 题解

注意到题目中有 $\left\lfloor\dfrac{b}{k}\right\rfloor=1+\left\lfloor\dfrac{a}{k}\right\rfloor$ 这个性质。

不难发现这个图可以每 $k$ 个点分一层，每层只有连向下一层的边。

可以发现每一层到下一层的最短路构成了一个 $k\times k$ 的矩阵。

设第 $i$ 层到 $i+1$ 层的最短路矩阵为 $A$，设第 $i+1$ 层到 $i+2$ 层的最短路矩阵为 $B$。

那么从设第 $i$ 层到 $i+2$ 层的最短路矩阵 $C$ 可以用 $C_{i,j}=\min\limits_{x=1}^k A_{i,x}+B_{x,j}$ 求出。

这是一个 $[+,\min]$ 矩阵，满足交换律和结合律。

构造完矩阵后，答案就是第 $\left\lfloor\dfrac{a}{k}\right\rfloor$ 层到第 $\left\lfloor\dfrac{b}{k}\right\rfloor$ 层最短路矩阵 $M$ 中的 $M_{a\bmod k,b\bmod k}$。

接下来就是如何计算第 $\left\lfloor\dfrac{a}{k}\right\rfloor$ 层到第 $\left\lfloor\dfrac{b}{k}\right\rfloor$ 层最短路矩阵 $M$。

观察到可以把 $\left\lfloor\dfrac{a}{k}\right\rfloor\sim \left\lfloor\dfrac{b}{k}\right\rfloor$ 拆成很多段，这样可以用倍增的思想解决。

设 $f_{i,j}$ 为第 $i$ 层到 $i+2^j$ 层的最短路矩阵，转移直接用 $f_{i,j}=f_{i,j-1}\times f_{i+2^{j-1},j-1}$。

把 $\left\lfloor\dfrac{a}{k}\right\rfloor\sim \left\lfloor\dfrac{b}{k}\right\rfloor$ 进行二进制拆分，就可以解决。

数据中有 $\left\lfloor\dfrac{a}{k}\right\rfloor=\left\lfloor\dfrac{b}{k}\right\rfloor$ 的数据，需要特判。

这题的空间只有 128MB，如果 MLE 可以尝试把数组开小。