P15604 [ICPC 2021 Jakarta R] Bicycle Tour

雅加达有 $N$ 个路口（编号从 $1$ 到 $N$），由 $M$ 条双向道路连接，使得从任意路口出发，可以通过一条或多条道路到达任何其他路口。第 $i$ 个路口的高度为 $H_i$。 艾哈迈德喜欢骑自行车，尤其喜欢在平坦的道路上骑行。他认为，如果道路是上坡或下坡，则需要更大的力气。具体来说，在连接路口 $i$ 和路口 $j$ 的道路上骑行所需的力气为 $|H_i - H_j|$。骑行一组道路所需的力气等于这些道路中所需力气的最大值。例如，有 $3$ 条道路，骑行每条道路分别需要 $10$、$12$ 和 $7$ 的力气，则骑行所有这些道路所需的力气为 $\max(10, 12, 7) = 12$。 从路口 $i$ 出发的骑行路线定义为一条始于路口 $i$，前往一个或多个其他路口，且不重复使用同一条道路，最后回到路口 $i$ 的环游路线。 艾哈迈德希望为每个路口找到一条所需力气最小的骑行路线，这就是本题的任务。对于每个路口，你需要输出从该路口出发的、具有最小所需力气的骑行路线所需的力气。可能存在从某个路口无法形成骑行路线的情况；此时，对应路口的输出应为 $-1$。 例如，设 $N = 8$，$H_{1..8} = \{5, 2, 7, 0, 10, 6, 6, 6\}$，$M = 11$，道路如下图所示。每个节点上的标签表示路口编号，每条边上的数字表示骑行该道路所需的力气。注意，每条道路所需的力气可由给定的 $H_{1..8}$ 计算得出。 :::align{center}  ::: 以下是从每个路口出发的具有最小所需力气的骑行路线： - 路口 $1$：$1 \rightarrow 2 \rightarrow 7 \rightarrow 6 \rightarrow 1$，所需力气为 $4$。 - 路口 $2$：$2 \rightarrow 1 \rightarrow 6 \rightarrow 7 \rightarrow 2$，所需力气为 $4$。 - 路口 $3$：$3 \rightarrow 2 \rightarrow 1 \rightarrow 3$，所需力气为 $5$。 - 路口 $4$：无法形成骑行路线。 - 路口 $5$：$5 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 5$，所需力气为 $8$。 - 路口 $6$：$6 \rightarrow 7 \rightarrow 8 \rightarrow 6$，所需力气为 $0$。 - 路口 $7$：$7 \rightarrow 8 \rightarrow 6 \rightarrow 7$，所需力气为 $0$。 - 路口 $8$：$8 \rightarrow 6 \rightarrow 7 \rightarrow 8$，所需力气为 $0$。

输入第一行包含两个整数 $N$ 和 $M$（$2 \leq N \leq 100\,000$；$N-1 \leq M \leq 200\,000$），分别表示路口数量和双向道路数量。第二行包含 $N$ 个整数 $H_i$（$0 \leq H_i \leq 10^9$），表示第 $i$ 个路口的高度。接下来 $M$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \leq u_i < v_i \leq N$），表示一条连接路口 $u_i$ 和 $v_i$ 的双向道路。保证从任意路口出发，可以通过一条或多条道路到达任何其他路口。同时保证对于任意一对路口 $(u, v)$，最多有一条双向道路连接它们。

输出一行 $N$ 个整数，每两个整数之间用一个空格隔开。第 $i$ 个整数表示从路口 $i$ 出发的具有最小所需力气的骑行路线所需的力气。如果从路口 $i$ 无法形成骑行路线，则第 $i$ 个整数为 $-1$。

翻译由 DeepSeek 完成