P13271

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