Skip to content

1181: 丁香之路

题目

题目描述

春暖花开,万物复苏,随着疫情的逐渐过去,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 的朋友们分别需要花费多少单位时间完成他们的目标。

输入格式

第一行 $3$ 个非负整数 $n, m$。保证 $1\le s\le n$ ;保证 $m\le \frac {n(n-1)}{2}$ 。

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

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

输出格式

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

样例输入

text 4 3 1 1 2 4 2 3 1

样例输出

text 6 7 8 7

数据范围

对于100%的数据中,满足1<=N<=2500。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!