#P1858. [省选联考 2020 B 卷] 丁香之路

    ID: 5381 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>基础算法贪心数据结构并查集图论生成树欧拉回路

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

题目描述

春暖花开,万物复苏,随着疫情的逐渐过去,Yazid 带着他的 nn 个好朋友来到 T 大校园参观游览。方便起见,我们将他们从 11nn 编号。

T 大校园的版图可以抽象成一张 nn 个顶点的无向图(顶点编号从 11nn)。且对于任意两个不同顶点,设它们的编号分别为 i,j(ij)i, j(i\neq j),则它们之间有一条需要花费 ij|i - j| 单位时间通过的无向边。

丁香花是 T 大的校花之一。时下正值丁香花盛开之际,校园内的 mm 条道路上都开有丁香花。Yazid 的朋友们对丁香花十分感兴趣,因此他们都希望遍历所有开有丁香花的 mm 条道路。

Yazid 的朋友们从顶点 ss 出发。其中,第 ii 个朋友希望以顶点 ii 为终点终止他的参观。与此同时,如上面所述,每个朋友都必须经过开着丁香花的 mm 条道路各至少一次。

Yazid 的朋友不想太过疲累,因此他们希望花尽可能少的时间来完成他们的目标。

请你计算 Yazid 的朋友们分别需要花费多少单位时间完成他们的目标。

输入格式

第一行 33 个非负整数 n,m,sn, m, s。保证 1sn1\le s\le n;保证 mn(n1)2m\le \frac {n(n-1)}2

22 行至第 m+1m+1 行,每行 22 个整数 u,vu, v,描述一条开有丁香花的,连接顶点 u,vu, v 的无向边。保证 1u,vn1\le u, v\le nuvu\neq v;保证每条无向边至多被描述一次。

对于输入的所有行,用单个空格将行内的多个整数隔开。

输出格式

输出一行 nn 个用单个空格隔开的整数,其中第 ii 个整数描述 Yazid 的第 ii 个朋友完成目标所需花费的最少时间。

4 3 1
1 2
4 2
3 1
6 7 8 7

11 个朋友的一种最优路线是从 11 出发依次途径 2,4,32, 4, 3,最终回到 11,消耗 12+24+43+31=6|1-2|+|2-4|+|4-3|+|3-1| = 6 单位时间。

22 个朋友的一种最优路线是从 11 出发依次途径 2,4,3,12, 4, 3, 1,最终来到 22,消耗 77 单位时间。

33 个朋友的一种最优路线是从 11 出发依次途径 2,4,12, 4, 1,最终来到 33,消耗 88 单位时间。

44 个朋友的一种最优路线是从 11 出发依次途径 3,1,23, 1, 2,最终来到 44,消耗 77 单位时间。

6 0 2
1 0 1 2 3 4

由于 m=0m = 0,没有必经之路,因此每个朋友直接通过一条边直达目的地即可。

5 4 1
1 2
3 4
4 5
3 5
8 7 6 7 8

数据范围/提示

测试点编号 n=n= 其他特殊限制
131\sim 3 5050 m=9m=9
464\sim 6 m=15m=15
787\sim 8
9109\sim 10 300300
1111 16001600 m=0m=0
121412\sim 14 m=1m=1
151715\sim 17
182018\sim 20 25002500