标签：虚点优化 | 靜海遺跡

Portal

​题目只有两个步骤：处理每个点的点权；跑一遍点权最短路。

​对于 $K$ 个城市，可以考虑把点权赋为 $\infty$ 。对于 $K$ 个点周围的点，可以 bfs 进行预处理。但当 $K$ 较大时，复杂度为 $O(kN)$, 与队列优化的 Bellman ford 相同。