P13271

Register_int · 2025-07-14 18:37:17 · 题解

一个看上去很笨的想法是：对于每个点 u，直接新建 k 个点 (u,i) 表示机器人到这里的参数。但这样实际上是对的，因为每个点只会有度数个参数是有用的，所以新建点数是 O(n) 的。修改参数就在点 u 的 (u,i) 内部建边，跑最短路即可。复杂度 O(n\log n)。