很板的最短路。 一眼看上去，我们要跑 nnn 次 dij，求出每个国家相互之间的最短距离，时间复杂度 O(nmlog⁡n)O(nm\log n)O(nmlogn)。 但其实并不用。 考虑建虚点。我们将每个国家向虚点建一个权值为售价的单向边，然后求各个国家与虚点的最短路即可。 但是这样还是 O(nmlog⁡n)O(nm\log n)O(nmlogn) 啊……是吗？ 注意到我们可以反向连边，则虚点到某个国家的最短路就是它到虚点的最短路。这样只需要跑一次 dij 即可。 时间复杂度：O(mlog⁡n)O(m\log n)O(mlogn)。