解题思路

每次配送都是从 1 号驿站走到目标驿站再返回 1 号。道路双向，最短路对称，因此一次往返的长度等于 1 号到该驿站最短路的两倍。

全部 $q$ 次配送互不影响，答案就是

2\sum_{i=1}^{q} \mathrm{dist}(1, x_i).

题目内容

地图上有 $n$ 个驿站，由 $m$ 条双向道路连接。你需要从 1 号驿站出发，把物资送到指定驿站后必须返回 1 号驿站，一共配送 $q$ 次。每次配送都从 1 号重新出发，互不影响。

请计算完成全部 $q$ 次往返配送所需的最短路程之和。

驿站数、道路数与配送次数均不超过 10^5。道路长度为不超过 10^4 的正整数。驿站编号为 1 到 $n$ 。保证给定的道路满足 $u eq v$ 。