笔试时间：2025年04月03日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目

假设你正在开发地图数据校验工具，其中有一个功能是检测城市的道路网络是否连通。具体来说，就是判断从任何一个地点出发，能否通过现有的道路到达其他任何地点。为此，我们需要设计一个算法来验证这一点。

输入描述

第一行包含两个整数 n 和 m，分别表示城市中有多少个地点以及有多少条双向道路。每个地点都有唯一的编号，范围是 [1, n]。

接下来 m 行，每行包含两个整数 a 和 b，表示地点 a 和地点 b 之间有一条双向道路相连。

输出描述

输出一行字符串，如果城市的所有地点都是相互连通的，则输出 "Yes"；否则，输出 "No"。

样例输入

5 6

0 1

0 2

1 3

2 3

3 4

1 4

样例输出

Yes

参考题解

用 邻接表（List） 存储图结构：graph[i] 存储 与地点 i 相连的所有地点。构建图。读取 m 条边，每条边连接 a 和 b，表示地点 a 和 b 之间有道路：由于是 无向图，所以 graph[a].add(b) 和 graph[b].add(a) 都需要添加。深度优先搜索（DFS）遍历。使用 visited[] 数组 记录哪些节点被访问过。从 0 号节点 开始执行 DFS，递归访问所有能到达的节点。判断连通性。遍历 visited[] 数组，检查是否所有节点都被访问：若 visited[i] == false（有未访问的节点），说明图不连通，输出 "No"。否则，输出 "Yes"，表示所有节点都能相互到达。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
using namespace std;

void dfs(const vector<vector<int>>& graph, int node, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> graph(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    vector<bool> visited(n, false);
    dfs(graph, 0, visited);

    bool isConnected = true;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            isConnected = false;
            break;
        }
    }

    cout << (isConnected ? "Yes" : "No") << endl;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class MapDataVerification {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 读取地点数量和道路数量
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        // 构建邻接表表示图
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // 读取每条道路的信息并添加到图中
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        // 标记节点是否被访问过
        boolean[] visited = new boolean[n];
        // 从节点 0 开始深度优先搜索
        dfs(graph, 0, visited);

        // 检查是否所有节点都被访问过
        boolean isConnected = true;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                isConnected = false;
                break;
            }
        }

        // 输出结果
        System.out.println(isConnected ? "Yes" : "No");
    }

    private static void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
        // 标记当前节点为已访问
        visited[node] = true;
        // 遍历当前节点的所有邻居节点
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfs(graph, neighbor, visited);
            }
        }
    }
}    

Python：[此代码未进行大量数据的测试，仅供参考]

def dfs(graph, node, visited):
    visited[node] = True
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    
    for _ in range(m):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    
    visited = [False] * n
    dfs(graph, 0, visited)
    
    is_connected = all(visited)
    print("Yes" if is_connected else "No")

if __name__ == "__main__":
    main()

第二题

题目

在导航app中，实现为用户推荐最近的3个充电桩的功能，需求如下：

给出用户所在位置，以及N个备选充电桩位置，返回距离用户最近且距离小于3km的前3个充电桩。

输入描述

第一行包含两个整数n和m，分别表示有向图中有多少个点以及有多少条边。每个点都有唯一的编号，范围是[0, n]。

第二行包含一个整数，为用户所在NodeID。

第三行包含一个整数k，为备选充电桩个数。

接下来k行，每行一个整数，为备选充电桩所在NodeID。

接下来m行，每行包含三个整数a、b、w，表示点a和点b之间有一条单向边，权重为w(单位米)。

输出描述

最近的充电桩的NodeID和距离，用"NodeID,Distance"表达，多个桩以";"分隔，若没有结果则返回"None" 。

样例输入

6 8

0

3

2

3

5

0 1 100

1 2 150

2 3 300

3 4 200

0 4 200

4 5 100

5 3 200

1 4 100

2 5 200

样例输出

2,2500;5,3000;3,3500

参考题解

构建图数据结构用 List<List<Edge>> 存储有向图，每个点存储连接的边（邻接表）。读取 m 条边的信息，建立图结构。Dijkstra 算法求最短路径使用 优先队列（堆） 维护当前最短路径。遍历所有可达点，更新到达该点的最短路径。筛选 & 排序筛选出 距离小于 3000m 的充电桩。按 距离升序排序，取 最近的 3 个。格式化输出按 NodeID,Distance 形式输出，多个桩用 ; 分隔。若无满足条件的充电桩，返回 "None"。复杂度分析Dijkstra 算法：O((N + M) log N)，N 是点数，M 是边数。充电桩筛选 & 排序：O(K log K)，K 是充电桩数。总体复杂度 ≈ O((N + M) log N) + O(K log K)，适用于 大规模地图数据。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

using namespace std;

struct Edge {
    int to, weight;
    Edge(int to, int weight) : to(to), weight(weight) {}
};

unordered_map<int, int> dijkstra(const vector<vector<Edge>>& graph, int start, int n) {
    unordered_map<int, int> distances;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, start});
    distances[start] = 0;
    
    while (!pq.empty()) {
        auto [dist, node] = pq.top(); pq.pop();
        if (dist > distances[node]) continue;
        for (const auto& edge : graph[node]) {
            int newDist = dist + edge.weight;
            if (!distances.count(edge.to) || newDist < distances[edge.to]) {
                distances[edge.to] = newDist;
                pq.push({newDist, edge.to});
            }
        }
    }
    return distances;
}

int main() {
    int n, m, userNode, k;
    cin >> n >> m >> userNode >> k;
    
    unordered_set<int> chargers;
    for (int i = 0; i < k; i++) {
        int charger;
        cin >> charger;
        chargers.insert(charger);
    }
    
    vector<vector<Edge>> graph(n);
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        graph[a].emplace_back(b, w);
    }
    
    auto distances = dijkstra(graph, userNode, n);
    
    vector<pair<int, int>> results;
    for (int charg