2026 华为OD机试真题9月23日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

小菊听说在一个神秘的城堡里藏着宝藏，她决定去寻宝。城堡由 n 个房间组成，某些房间之间有通道相连。小菊从房间 s 出发，想要到达藏有宝藏的房间 t。

给定房间数量 n、通道列表 edges、起点 s 和终点 t，求小菊从起点到终点经过通道最短的路径长度。所有通道长度相同且均为 1，例如房间 1 → 2 → 3 经过两条通道，路径长度为 2。

如果起点和终点相同，返回 0；如果终点无法到达，返回 -1。

2026 华为OD机试真题9月23日华为OD上机新系统考试真题 100 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

输入描述

第一行输入房间数量 n，满足 1 ≤ n ≤ 10000，房间编号为 1 到 n。

第二行输入二维数组 edges，表示无向通道列表。边数 m 满足 0 ≤ m ≤ 100000，允许自环和重边。

第三行输入起点 s，第四行输入终点 t，满足 1 ≤ s,t ≤ n。

输出描述

输出从起点 s 到终点 t 的最短路径长度。若 s=t 则输出 0；若终点不可达则输出 -1。

示例1

输入

4
[[1, 2], [2, 3], [3, 4], [1, 3]]
1
4

输出

2

说明

最短路径为房间 1 → 3 → 4，共经过两条通道。

示例2

输入

4
[[1, 2], [2, 1], [3, 4], [4, 3]]
1
3

输出

-1

说明

房间 1、2 和房间 3、4 分属两个连通分量，无法从房间 1 到达房间 3。

示例3

输入

5
[]
1
1

输出

说明

起点与终点相同，无需经过任何通道。

示例4

输入

4
[[1, 1], [1, 2], [2, 3], [3, 4]]
1
4

输出

3

说明

自环 [1,1] 不会缩短路径，最短路径为 1 → 2 → 3 → 4。

示例5

输入

6
[[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [1, 6], [2, 5]]
1
6

输出

1

说明

房间 1 和房间 6 之间存在直接通道，最短路径长度为 1。

解题思路

本题采用【广度优先搜索】算法：所有通道的长度都为 1，从起点开始按层扩展时，先访问到的房间一定具有更短的路径，因此 BFS 可以直接求出无权图中的最短距离。

先根据 edges 建立无向图的邻接表，再使用数组记录每个房间到起点的距离，初始值为 -1 表示尚未访问。起点距离设为 并加入队列，每次取出队首房间，将所有未访问的相邻房间距离更新为当前距离加一。

第一次访问终点时即可立即返回其距离。如果队列为空后仍未访问终点，说明两者不连通，返回 -1。起点和终点相同时直接返回