题目描述

小红参加了一个闯关游戏，游戏地图是一个迷宫，一共有 $n$ 个地点，并且这 $n$ 个地点通过 $m$ 条路进行联通。

由于游戏规则要求，小红每次要从起点( $1$ 号节点)取一面旗帜，并放到官方要求的地点，然后返回起点，直到将所有旗送完。

思路：最短路-堆优化Dijkstra

本题是一道堆优化的 Dijkstra 模板题。

每次从 $1$ 号点到达 $x$ 号点后，需要从 $x$ 号点再返回 $1$ 号点。 有 $q(1\leq q < 10^5)$ 次询问，所以单次时间复杂度不能超过 $O(\log n)$

从 $1$ 号点到达 $x$ 号点的最短距离，必然也是从 $x$ 号点到达 $1$ 号点的最短距离。所以相当于到达每个点再返回的总距离就是从 $1$ 号点到达给定 $q$ 个点的总距离乘 $2$ 。

这就是一个单源最短路径问题，由于数据规模是 $1\leq n,m < 10^5$ ，所以需要堆优化的 Dijkstra 来解决。