这道题明显是最短路，要用dijkstra+堆优化，但需要稍微改变一下， 题目分析 给定一个带权无向图、目标顶点s和q个顶点，求这q个顶点到s的最短路。 朴素做法是对于每个顶点都跑一遍dijkstra，但q的范围是1≤q≤2×1051≤q≤2\times10^51≤q≤2×105，这样时间复杂度为O(qmlog⁡n)O(qm\log n)O(qmlogn)，最坏情况下要执行约7×10117\times 10^{11}7×1011次，显然超时。 这时候就该考虑将多源最短路转换成单源最短路，由于是无向图，那么我们可以反着计算，只需计算从顶点sss到各个顶点的距离即可。对于无向图来讲，s→ts\rightarrow ts→t和t→st\rightarrow st→s的最短路等价。 时间复杂度：O(q+mlog⁡n)O(q+m\log n)O(q+mlogn)