🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 120+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🌈 华为秋招(海外留学生版)笔试，来啦！！！

🍥 留学生的题目难度相对于国内来说总体来看会简单一丢丢，但整体题目风格，难度，几乎都是一样的哦～

tips 国内的有些题会复用留学生考过的题目哦，国内机考的朋友可以把留学生的题目也刷一刷

本次的 第一题 和 第三题 分别是国内校招 9.27 和 10.9 的原题，懂得都懂，无须多言

1️⃣ BFS+思维题，难度较大，有细节和坑点

2️⃣ 并查集+模拟+排序，考查的比较全面

3️⃣ 据说是暴力DFS能过，比较诈骗，大家实际考试的时候可以直接暴力骗分哦～

🌲 01.环保出行计划 评测链接🔗

问题描述

LYA 是一位热衷于环保的上班族。为了减少碳排放，她每天都选择乘坐公共交通工具上班。城市的公交系统由多条单向循环路线组成，每条路线都有固定的站点序列。例如，25 路公交的路线为 ，那么公交车会按照 的顺序循环行驶。

LYA 的日常通勤路线包括三个关键站点：最近的上车站、最喜欢的早餐店所在站点，以及离公司最近的下车站。她希望在保证买到早餐的前提下，用最少的换乘次数完成整个通勤过程。

你的任务是帮助 LYA 规划最优的乘车路线，使得她乘坐的公交车总数最少。需要注意的是，如果在同一条公交路线中下车再上车，仍然视为乘坐同一辆车。

输入格式

第一行包含 3 个整数 、、，分别表示 LYA 的上车站点编号、早餐店所在站点编号和下车站点编号。

第二行包含一个整数 ，表示公交路线的数量。

接下来的 行，每行描述一条公交路线。每行的第一个整数 表示该路线的站点数量，后面跟着 个整数，表示该路线经过的站点编号（按顺序排列）。

输出格式

输出一个整数，表示 LYA 需要乘坐的公交车数量的最小值。如果无法找到满足条件的路线，输出 。

样例输入 1

1 3 5
4
3 1 2 6
3 2 3 7
3 5 6 8
2 5 7

样例输出 1

3

样例解释 1

LYA 可以按以下路线行进：

1. 在站点 1 乘坐第一条路线的公交车。
2. 在站点 2 下车，换乘第二条路线的公交车。
3. 在站点 3 下车购买早餐，然后继续乘坐第二条路线的公交车。
4. 在站点 7 下车，换乘第四条路线的公交车。
5. 最终在站点 5 下车到达公司。

总共乘坐了 3 辆不同的公交车（），因此输出 3。

样例输入 2

1 3 4
2 
3 1 2 4
3 3 5 6

样例输出 2

-1

样例解释 2

LYA 只能乘坐第 1 条公交路线上车，但无法通过该路线的站台换乘到第 2 条公交路线购买早餐，因此没有匹配的路线，返回 -1。

样例输入 3

4 19 28
5
5 3 4 7 8 10
6 10 12 16 19 27 28
4 5 7 11 17
4 17 19 22 23
3 23 27 28

样例输出 3

2

样例解释 3

LYA 可以选择 的公交路线，乘坐的公交车总数为 2。虽然也可以选择 的公交路线，但这样需要乘坐 4 辆公交车。因此，最佳的乘车路线是 ，结果为 2。

数据范围

• 公交路线数量 的范围：。
• 公交站台编号的范围：。
• 每条公交路线经过的站台数量范围：。
• 保证起点站台、早餐站点和终点站台互不相同。
• 每条路线中的站台编号按升序排列，且不包含重复的站台。

题解

两次BFS+思维

关键点在于理解题目的特殊规则：在早餐店换乘同一辆车不算额外的换乘次数。这就好比在早餐店门口下车，买完早餐后又坐回同一辆车，这种情况下不需要额外付车费。

解决这个问题的思路其实很直观。首先，从起点出发，找到到达早餐店的最短路径。然后，从早餐店出发，找到到达公司的最短路径。这两段路径加起来就是整个旅程的最优解。

具体来说，可以使用两次（BFS）来实现：

1. 第一次BFS：从起点到早餐店。
2. 第二次BFS：从早餐店到公司。

在第二次BFS中，需要特别注意处理在早餐店的特殊换乘规则。如果某条路线经过早餐店，那么在这条路线上继续前进不需要增加换乘次数。

举个例子，假设有以下公交路线：

1号线：1 -> 2 -> 3 -> 4
2号线：2 -> 5 -> 6
3号线：4 -> 5 -> 7

起点在1，早餐店在4，终点在7。

第一次BFS会得到路径：1 -> 2 -> 3 -> 4（1号线），换乘次数为0。 标记1号线为包含早餐店的路线。

第二次BFS时，从4出发：

• 可以直接使用1号线到达其他站点，不增加换乘次数。
• 使用3号线时需要增加换乘次数。

最终路径可能是：1 -> 2 -> 3 -> 4（1号线）-> 5 -> 7（3号线），总换乘次数为 1。

参考代码

• Python

from collections import deque

MAX_STATIONS = 1000005  # 最大站点数
MAX_ROUTES = 505  # 最大路线数

# 初始化全局变量
dist_to_breakfast = [0] * MAX_STATIONS  # 存储从起点到每个站点的距离
dist_from_breakfast = [0] * MAX_STATIONS  # 存储从早餐店到每个站点的距离
visited = [0] * MAX_STATIONS  # 用于BFS中标记已访问的路线
breakfast_route = [0] * MAX_ROUTES  # 标记哪些路线包含早餐店
route_first_visit = [0] * MAX_ROUTES  # 记录每条路线首次被访问的时间
station_to_routes = [[] for _ in range(MAX_STATIONS)]  # 存储每个站点所属的路线
routes = []  # 存储每条路线经过的站点

def bfs_to_breakfast(start, breakfast):
    q = deque([start])
    dist_to_breakfast[start] = 1  # 起点距离设为1
    while q:
        current = q.popleft()
        for route in station_to_routes[current]:
            if not visited[route]:
                route_first_visit[route] = dist_to_breakfast[current] + 1
                for station in routes[route]:
                    if not dist_to_breakfast[station]:
                        dist_to_breakfast[station] = dist_to_breakfast[current] + 1
                        q.append(station)
                visited[route] = 1  # 标记路线为已访问
    
    # 标记包含早餐店的路线
    for i in range(1, len(routes)):
        if route_first_visit[i] == dist_to_breakfast[breakfast]:
            if breakfast in routes[i]:
                breakfast_route[i] = 1

def bfs_from_breakfast(breakfast, end):
    global visited
    visited = [0] * MAX_STATIONS  # 重置visited数组
    q = deque([breakfast])
    dist_from_breakfast[breakfast] = 1  # 早餐店距离设为1
    while q:
        current = q.popleft()
        for route in station_to_routes[current]:
            if not visited[route]:
                distance = dist_from_breakfast[current] + 1
                if breakfast_route[route]:
                    distance -= 1  # 如果是包含早餐店的路线，不增加换乘次数
                for station in routes[route]:
                    if not dist_from_breakfast[station]:
                        dist_from_breakfast[station] = distance
                        q.append(station)
                visited[route] = 1  # 标记路线为已访问

def solve():
    # 读取输入
    start, breakfast, end = map(int, input().split())
    num_routes = int(input())
    global routes
    routes = [[] for _ in range(num_routes + 1)]  # 路线编号从1开始
    for i in range(1, num_routes + 1):
        route = list(map(int, input().split()))
        routes[i] = route[1:]  # 第一个数字是站点数量，跳过
        for station in routes[i]:
            station_to_routes[station].append(i)
    
    # 执行从起点到早餐店的BFS
    bfs_to_breakfast(start, breakfast)
    if not dist_to_breakfast[breakfast]:
        print(-1)  # 无法到达早餐店
        return
    
    # 执行从早餐店到终点的BFS
    bfs_from_breakfast(breakfast, end)
    if not dist_from_breakfast[end]:
        print(-1)  # 无法到达终点
        return
    
    # 计算并输出结果
    print(dist_to_breakfast[breakfast]+ dist_from_breakfast[end] - 2)

solve()  # 执行主函数

• Java

import java.util.*;

public class Main {
    static final int MAX_STATIONS = 1000005;  // 最大站点数
    static final int MAX_ROUTES = 505;  // 最大路线数

    // 初始化全局变量
    static long[] dist_to_breakfast = new long[MAX_STATIONS];  // 存储从起点到每个站点的距离
    static long[] dist_from_breakfast = new long[MAX_STATIONS];  // 存储从早餐店到每个站点的距离
    static int[] visited = new int[MAX_STATIONS];  // 用于BFS中标记已访问的路线
    static int[] breakfast_route = new int[MAX_ROUTES];  // 标记哪些路线包含早餐店
    static long[] route_first_visit = new long[MAX_ROUTES];  // 记录每条路线首次被访问的时间
    static List<List<Integer>> station_to_routes = new ArrayList<>();  // 存储每个站点所属的路线
    static List<List<Integer>> routes = new ArrayList<>();  // 存储每条路线经过的站点

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        for (int i = 0; i < MAX_STATIONS; i++) {
            station_to_routes.add(new ArrayList<>());
        }
        solve(scanner);
    }

    static void bfs_to_breakfast(int start, int breakfast) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        dist_to_breakfast[start] = 1;  // 起点距离设为1
        while (!q.isEmpty()) {
            int current = q.poll();
            for (int route : station_to_routes.get(current)) {
                if (visited[route] == 0) {
                    route_first_visit[route] = dist_to_breakfast[current] + 1;
                    for (int station : routes.get(route)) {
                        if (dist_to_breakfast[station] == 0) {
                            dist_to_breakfast[station] = dist_to_breakfast[current] + 1;
                            q.offer(station);
                        }
                    }
                    visited[route] = 1;  // 标记路线为已访问
                }
            }
        }
        
        // 标记包含早餐店的路线
        for (int i = 1; i < routes.size(); i++) {
            if (route_first_visit[i] == dist_to_breakfast[breakfast]) {
                if (routes.get(i).contains(breakfast)) {
                    breakfast_route[i] = 1;
                }
            }
        }
    }

    static void bfs_from_breakfast(int breakfast, int end) {
        Arrays.fill(visited, 0);  // 重置visited数组
        Queue<Integer> q = new LinkedList<>();
        q.offer(breakfast);
        dist_from_breakfast[breakfast] = 1;  // 早餐店距离设为1
        while (!q.isEmpty()) {
            int current = q.poll();
            for (int route : station_to_routes.get(current)) {
                if (visited[route] == 0) {
                    long distance = dist_from_breakfast[current] + 1;
                    if (breakfast_route[route] == 1) {
                        distance--;  // 如果是包含早餐店的路线，不增加换乘次数
                    }
                    for (int station : routes.get(route)) {
                        if (dist_from_breakfast[station] == 0) {
                            dist_from_breakfast[station] = distance;
                            q.offer(station);
                        }
                    }
                    visited[route] = 1;  // 标记路线为已访问
                }
            }
        }
    }

    static void solve(Scanner scanner) {
        // 读取输入
        int start = scanner.nextInt();
        int breakfast = scanner.nextInt();
        int end = scanner.nextInt();
        int num_routes = scanner.nextInt();
        
        routes.add(new ArrayList<>());  // 添加一个空列表，使路线编号从1开始
        for (int i = 1; i <= num_routes; i++) {
            int num_stations = scanner.nextInt();
            List<Integer> route = new ArrayList<>();
            for (int j = 0; j < num_stations; j++) {
                int station = scanner.nextInt();
                route.add(station);
                station_to_routes.get(station).add(i);
            }
            routes.add(route);
        }
        
        // 执行从起点到早餐店的BFS
        bfs_to_breakfast(start, breakfast);
        if (dist_to_breakfast[breakfast] == 0) {
            System.out.println(-1);  // 无法到达早餐店
            return;
        }
        
        // 执行从早餐店到终点的BFS
        bfs_from_breakfast(breakfast, end);
        if (dist_from_breakfast[end] == 0) {
            System.out.println(-1);  // 无法到达终点
            return;
        }
        
        // 计算并输出结果
        System.out.println(dist_to_breakfast[breakfast] + dist_from_breakfast[end] - 2);
    }
}

• Cpp

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int MAX_STATIONS = 1000005;  // 最大站点数
const int MAX_ROUTES = 505;  // 最大路线数

// 全局变量声明
int dist_to_breakfast[MAX_STATIONS], dist_from_breakfast[MAX_STATIONS];  // 存储两次BFS的距离
int visited[MAX_STATIONS];  // 用于BFS中标记已访问的路线
int breakfast_route[MAX_ROUTES];  // 标记哪些路线包含早餐店
int route_first_visit[MAX_ROUTES];  // 记录每条路线首次被访问的时间
vector<int> station_to_routes[MAX_STATIONS];  // 存储每个站点所属的路线
vector<vector<int>> routes;  // 存储每条路线经过的站点

// 从起点到早餐店的BFS
void bfs_to_breakfast(int start, int breakfast) {
    queue<int> q;
    q.push(start);
    dist_to_breakfast[start] = 1;  // 起点距离设为1
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (auto route : station_to_routes[current]) { 
            if (!visited[route]) {
                route_first_visit[route] = dist_to_breakfast[current] + 1;
                for (auto station : routes[route]) {
                    if (!dist_to_breakfast[station]) {
                        dist_to_breakfast[station] = dist_to_breakfast[current] + 1;
                        q.push(station);
                    }
                }
                visited[route] = 1;  // 标记路线为已访问
            }
        }
    }
    // 标记包含早餐店的路线
    for (int i = 1; i < routes.size(); i++) {
        if