分数: 6 点
警告
2020 年 12 月 27 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
在一个城市里,有 N 村庄,编号 1 通过 N。村庄海拔 i is H_i。没有两个村庄处于同一海拔。
有 M 水道,每条水道连接两个村庄;的 i第水道连接村庄 A_i 和村庄 B_i。从海拔较高的村庄到海拔较低的村庄只能通过水路。
在这座城市, K 村庄-村庄 C_1, C_2, C_3, \dots, C_K - 被指定为灾难发生时的避难所。
对于每个村庄,确定是否可以使用零个或多个水路到达避难地点之一。如果可能的话,还求出从该村庄到达避难所必须经过的最少水道数量。
约束
- 2 \le N \le 2 \times 10^5
- 1 \le M \le 2 \times 10^5
- 1 \le K \le N
- 1 \le H_i \le 10^9
- H_i \neq H_j (i \neq j)
- 1 \le C_i \le N
- C_i \neq C_j (i \neq j)
- 1 \le A_i \le N
- 1 \le B_i \le N
- A_i \neq B_i
- (A_i, B_i) \neq (A_j, B_j) (i \neq j)
- (A_i, B_i) \neq (B_j, A_j) (i \neq j)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M K
H_1 H_2 H_3 \dots H_N
C_1 C_2 C_3 \dots C_K
A_1 B_1
A_2 B_2
A_3 B_3
\hspace{15pt} \vdots
A_M B_M
输出
打印 N 行。如果从村庄可以到达避难所 i, i- 第行应包含到达避难地点必须经过的最少水道数量;否则,该行应包含 -1.
示例输入 1
5 5 2 1 2 3 4 5 1 2 1 2 1 3 4 2 4 3 3 5
示例输出 1
0 0 1 1 2
- 村 1:由于它本身就是一个避难所,因此必须穿越的最少水道数是 0.
- 村 2:由于它本身就是一个避难所,因此必须穿越的最少水道数是 0.
- 村 3: 因为它的海拔高于村庄 1,我们可以遍历 2-去村的水路 1,这是一个避难所。我们走过了 1 水路,这是所需的最小数量。
- 村 4: 因为它的海拔高于村庄 2,我们可以遍历 3-rd水路去村 2,这是一个避难所。我们走过了 1 水路,这是所需的最小数量。
- 村 5:我们可以遍历 5第条水路去村 3,然后遍历 2-去村的水路 1,这是一个避难所。我们走过了 2 水路,这是所需的最小数量。
示例输入 2
5 6 2 6 5 9 15 3 4 2 1 5 2 5 2 4 1 3 4 3 2 1
示例输出 2
1 0 2 0 -1
来自村庄 5,我们不能去任何其他村庄。它本身也不是避难所,所以 5- 第行应包含 -1.
示例输入 3
5 4 2 3 10 5 8 2 3 5 3 2 3 1 4 5 2 1
示例输出 3
-1 1 0 1 0