华为OD机考双机位C卷 - Alice的安全旅行 （Java Python JS GO C++ C）

Alice的安全旅行

2026华为OD机试双机位C卷 - 华为OD上机考试双机位C卷

华为OD机试双机位C卷真题目录点击查看: 【全网首发】2026华为OD机位C卷 机考真题题库含考点说明以及在线OJ（OD上机考试双机位C卷）

题目描述

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

示例1

输入

4 3 8 10 7 10 3 0 1 0 2 2 3

输出

7

说明

解题思路

核心思想

本题要求寻找一条从城市 0 到城市 N-1 的路径，使得路径上所有城市安全度的最小值尽可能大，同时路径长度（经过的城市总数）不能超过 K。

这是一个典型的最大化最小值问题，通常可以使用二分答案（Binary Search on Answer）来解决。

1. 二分答案: 假设我们设定一个安全度阈值X XX。如果存在一条路径，满足以下条件，则说明X XX是可行的：

   • 路径上所有城市（包括起点和终点