OD 机试真题：Alice 的安全旅行 - 路径最大安全度

Alice 计划从城市 0 出发最终到达城市 N-1，他可以选择一条路线，但路上经过的城市总数（包括起点和终点）不能超过 K 个。每个城市都有一个安全度值，整个旅程的安全度被定义为路径上所有城市安全度的最小值。她的目标是让这个最小值尽可能高，请问 Alice 的旅程总体安全度最大能为多少？

第一行有两个整数 N 和 K，表示一共 N 个城市，以及 Alice 最多去 K 个城市（2 < N < 100000，1 < K < 100000）。

接下来 N 行，每行包括一个整数 h，表示去某个城市的安全度（0 <= h <= 1000000000）。

接下来一行有一个整数 M，表示城市间的 M 条道路（0 < M < 200000）。

接下来 M 行，每行有两个整数 s0 s1，表示城市 s0 和 s1 之间有双向道路相通。

一个整数，表示 Alice 这趟旅行的最大安全度，若不存在符合条件的路线，返回 -1。

更多推荐文章