题解：P11875 衡量距离

· · 题解

首先看到可达性问题，而且 N 的范围不大，并且 k 的值很大，就很难不想到矩阵快速幂。

但是这个题和普通的题不同，这个题的边权 w\leq 10 不能用朴素版本来做，但是可以考虑把每个点拆成 10 个点使得他们变成一条链的形态，具体建边的方式如下：

  1. 把每个点拆成 10 个点，我们称他叫做点 i 的附属点。第 i 个点的第 j 个附属点的编号为 i+(j-1)\times n 这样编号的好处就是不会重复，避免边和边之间的交叉问题。
  2. 连边的时候，首先第 i 个点的第 j 个附属点向第 i 个点的第 j+1 个附属点连边，可以保证 i 的附属点是一条链的结构。
  3. 连那 M 条边的时候，设边权为 w 则把 u 的第 w 个附属点向 v 连边。

这样我们就构造好了初始矩阵，接下来考虑矩阵快速幂的时候如何更新矩阵。

由于我们每个点增加了 10 个附属点，所以现在一共有 10\times n 个节点，也就是 1000 级别，如果直接上矩阵快速幂并且使用朴素版更新的话是 O(n^3\log k) 的，这里 n\leq 1000 所以无法接受，我们发现在更新的时候实际上是类似于一个传递闭包的形式的，并且 j 的那一维是没有用的所以可以使用 bitset 优化它，这样时间复杂度就变成了 O(\frac{n^3}{w} \log k) 可以通过。

代码