~ Esoteria Algorithm in Reverse Observatory

LGOJ P3393 | 逃离僵尸岛

Portal

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

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