分数: 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