自动搬运

查看原文

来自洛谷，原作者为

	EuphoricStar Remember.

搬运于2025-08-24 22:47:49，当前版本为作者最后更新于2023-12-15 12:53:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

复读官方题解。

考虑除了原图的 $2^k$ 个点，再建一些辅助点，$(u, i, j)$ 表示前 $i$ 位中修改了 $j$ 位得到 $u$。那么除了原图的 $m$ 条边，我们还有下面这些边：

• $u \xrightarrow{0} (u, 0, 0)$；
• $\forall i < k, (u, i, j) \xrightarrow{0} (u, i + 1, j)$；
• $\forall i < k, (u, i, j) \xrightarrow{0} (u \oplus 2^i, i + 1, j + 1)$；
• $(u, k, j) \xrightarrow{a_j} u$。

到这里可以做 $O(2^k k^3)$，但是还不够。

观察这个图，发现非 $0$ 边仅有 $O(2^k k)$ 条，于是我们在外层 Dijkstra 的同时，内层对 $u$ 能到达的所有辅助点跑一遍 BFS，给每个辅助点打上是否被访问过的标记，于是每个辅助点只会被访问一次，又因为非 $0$ 边仅有 $O(2^k k)$ 条，所以外层的堆也只会被 push 这么多次。所以时间复杂度就是 $O(2^k k^2)$，空间复杂度也是 $O(2^k k^2)$。

code