← 返回题目列表

AtCoder · awc0093_d

D. 登山路线的选择

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥正在计划在山区进行徒步旅行。这个山区有 N 位置,每个编号自 1 to N。这些位置通过以下方式连接 M 双向山间小道。但是,不能保证所有位置都可以通过路径相互到达。

每个地点 i (1 \leq i \leq N) 具有海拔 H_i.

Takahashi 想要选择从该位置出发的路线 1 (步道起点)和到达位置 N (山顶观景台)。在这里,一个 路线 是位置序列 p_1, p_2, \ldots, p_L 满足以下所有条件:

  • p_1 = 1 和 p_L = N.
  • 对于所有人 1 \leq k \leq L-1,存在山路连接位置 p_k 和位置 p_{k+1}.
  • p_1, p_2, \ldots, p_L 都是不同的(没有位置被访问超过一次)。

地点数量 包含在路线中的 L 称为 航路点数量 该路线的 。航路点的数量包括起始位置 1 和目的地位置 N。由以上条件可知, L \geq 2.

此外,沿路线访问的所有地点的最大海拔,即 \max(H_{p_1}, H_{p_2}, \ldots, H_{p_L}),称为 最大海拔 该路线的 。

路线的最高海拔越高,发生高原反应的风险就越大。高桥希望尽可能降低高原反应的风险。另一方面,选择经过很多地点的路线会耗尽他的体力。因此,高桥决定从航点数量较多的航线中进行选择。 L 最多是 K.

在最多有多个航路点的所有航线中 K,找到可实现的最小值 最大海拔 该路线的.

如果不存在有效路线(即无法到达位置 N 来自位置 1 最多 K 航点),输出 -1.

约束

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 2 \leq K \leq N
  • 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
  • 最多有一条路径连接任意一对位置(无多边)
  • 没有自环
  • 图不一定相连
  • 所有输入值均为整数

输入

N M K
H_1 H_2 \ldots H_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
  • 第一行包含位置数 N,路径数 M,以及航点数量上限 K,用空格分隔。
  • 第二行包含每个位置的海拔 H_1, H_2, \ldots, H_N,用空格分隔。
  • 在下面 M lines, the j第行 (1 \leq j \leq M) 包含两个位置 U_j 和 V_j 由 j第一条路径,以空格分隔。

输出

如果存在有效路线,则在一行中输出可达到的最小最大海拔。如果不存在有效路由,则输出 -1.


示例输入 1

5 6 4
10 50 30 20 40
1 2
2 3
3 5
1 4
4 5
2 5

示例输出 1

40

示例输入 2

4 3 2
1 2 3 4
1 2
2 3
3 4

示例输出 2

-1

示例输入 3

8 10 5
5 100 3 7 200 4 8 6
1 2
1 3
2 5
3 4
4 6
6 7
7 8
5 8
2 8
3 7

示例输出 3

8

示例输入 4

10 15 4
10 500 20 15 300 25 12 8 400 30
1 2
1 3
1 7
2 5
3 4
4 6
6 10
7 8
8 10
5 10
2 10
3 10
4 10
7 10
9 10

示例输出 4

30

示例输入 5

2 1 2
1000000000 1
1 2

示例输出 5

1000000000