P9377 题解

EuphoricStar · 2023-12-15 12:53:14 · 题解

复读官方题解。

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

到这里可以做 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