P6628 [省选联考 2020 B 卷] 丁香之路

春暖花开，万物复苏，随着疫情的逐渐过去，Yazid 带着他的 $n$ 个好朋友来到 T 大校园参观游览。方便起见，我们将他们从 $1$ 至 $n$ 编号。 T 大校园的版图可以抽象成一张 $n$ 个顶点的无向图（顶点编号从 $1$ 至 $n$）。且对于任意两个不同顶点，设它们的编号分别为 $i, j(i\neq j)$，则它们之间有一条需要花费 $|i - j|$ 单位时间通过的无向边。 丁香花是 T 大的校花之一。时下正值丁香花盛开之际，校园内的 $m$ 条道路上都开有丁香花。Yazid 的朋友们对丁香花十分感兴趣，因此他们都希望遍历**所有**开有丁香花的 $m$ 条道路。 Yazid 的朋友们从顶点 $s$ 出发。其中，第 $i$ 个朋友希望以顶点 $i$ 为终点终止他的参观。与此同时，如上面所述，每个朋友都必须经过开着丁香花的 $m$ 条道路各至少一次。 Yazid 的朋友不想太过疲累，因此他们希望花尽可能少的时间来完成他们的目标。 请你计算 Yazid 的朋友们分别需要花费多少单位时间完成他们的目标。

无

无

**样例解释 1** 第 $1$ 个朋友的一种最优路线是从 $1$ 出发依次途径 $2, 4, 3$，最终回到 $1$，消耗 $|1-2|+|2-4|+|4-3|+|3-1| = 6$ 单位时间。 第 $2$ 个朋友的一种最优路线是从 $1$ 出发依次途径 $2, 4, 3, 1$，最终来到 $2$，消耗 $7$ 单位时间。 第 $3$ 个朋友的一种最优路线是从 $1$ 出发依次途径 $2, 4, 1$，最终来到 $3$，消耗 $8$ 单位时间。 第 $4$ 个朋友的一种最优路线是从 $1$ 出发依次途径 $3, 1, 2$，最终来到 $4$，消耗 $7$ 单位时间。 **样例解释 2** 由于 $m = 0$，没有必经之路，因此每个朋友直接通过一条边直达目的地即可。 **数据范围与约定** | 测试点编号 | $n=$ | 其他特殊限制 | | --------- | ---- | ---------- | | $1\sim 3$ | $50$ | $m=9$ | | $4\sim 6$ | $50$ | $m=15$ | | $7\sim 8$ | $50$ | | | $9\sim 10$ | $300$ | | | $11$ | $1600$ | $m=0$ | | $12\sim 14$ | $1600$ | $m=1$ | | $15\sim 17$ | $1600$ | | | $18\sim 20$ | $2500$ | |