~ Esoteria Algorithm in Reverse Observatory
Portal
题目只有两个步骤:处理每个点的点权;跑一遍点权最短路。
对于 KKK 个城市,可以考虑把点权赋为 ∞\infty∞ 。对于 KKK 个点周围的点,可以 bfs 进行预处理。但当 KKK 较大时,复杂度为 O(kN)O(kN)O(kN), 与队列优化的 Bellman ford 相同。