笔试时间：2025年8月30日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

现在有赛事要在一山区举行，山区内有n个打卡点（编号为1~n），打卡点之间有m条可供通行的山路，每条山路都需要花费确定的通行时间（单位：分钟）。赛事要求选手从“起点打卡点”出发，最终到达“终点打卡点”。组委会在某两个打卡点A和B之间设置了一条特殊索道，选手可以通过该索道在这两个打卡点之间瞬间往返（不消耗时间）。请计算选手从起点到终点的最短通行时间（保证存在可达路径）。

输入描述

第一行两个正整数n,m，分别表示打卡点总数和山路数量。

第二行两个正整数，分别表示“起点打卡点”和“终点打卡点”的编号。

第三行两个正整数，分别表示设有特殊索道的两个打卡点的编号。

接下来m行，每行三个正整数u,v,t，分别表示打卡点u和v之间有一条山路，双向通行，通过该山路需要耗时t分钟。

输入约束

1 ≤ n ≤ 100

1 ≤ m < 2 × n

每条道路的时间花在 [1,10] 之间。

输出描述

一个整数表示最短通行时间。

样例输入

6 5

2 6

3 5

3 3 3

3 4 2

4 5 1

5 6 4

2 4 5

样例输出

7

参考题解

C++：

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

// 定义无穷大（需足够大，避免累加溢出，long long类型）
const long long INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // 加速输入输出
    
    // 读取输入：n(节点数)、m(边数)、s(起点)、e(终点)、a/b(中间点)
    int n, m, s, e, a, b;
    cin >> n >> m >> s >> e >> a >> b;
    
    // 初始化邻接矩阵：(n+1)x(n+1)（节点1-based），默认无穷大
    vector<vector<long long>> d(n + 1, vector<long long>(n + 1, INF));
    // 自身到自身的距离为0
    for (int i = 1; i <= n; ++i) {
        d[i][i] = 0;
    }
    
    // 读取m条无向边，更新邻接矩阵（取最小权值，处理重边）
    for (int i = 0; i < m; ++i) {
        int x, y;
        long long z; // 边权用long long，避免溢出
        cin >> x >> y >> z;
        // 无向边：x→y和y→x距离相同，取最小值
        if (z < d[x][y]) {
            d[x][y] = z;
            d[y][x] = z;
        }
    }
    
    // Floyd-Warshall算法：计算所有节点对的最短路径
    for (int k = 1; k <= n; ++k) { // k：中间节点
        for (int i = 1; i <= n; ++i) { // i：起点
            for (int j = 1; j <= n; ++j) { // j：终点
                // 若i→k和k→j均可达，更新i→j的最短路径
                if (d[i][k] != INF && d[k][j] != INF) {
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
    }
    
    // 计算三种目标路径的长度
    long long p1 = d[s][e];                  // 直接s→e
    long long p2 = d[s][a] + d[b][e];        // s→a → b→e
    long long p3 = d[s][b] + d[a][e];        // s→b → a→e
    
    // 取最小值作为答案
    long long ans = min({p1, p2, p3}); // C++11及以上支持初始化列表min
    cout << ans << endl;
    
    return 0;
}

Java：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Iterator;
import java.util.StringTokenizer;

public class Main {
    // 定义无穷大（long类型，避免累加溢出）
    private static final long INF = 1000000000000000000L; // 1e18

    public static void main(String[] args) throws IOException {
        // 读取所有输入，分割为token，用迭代器遍历（模拟Python的iter）
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 手动维护迭代器（因输入可能分多行，此处简化为逐token读取）
        Iterator<String> tokenIter = new Iterator<>() {
            @Override
            public boolean hasNext() {
                while (!st.hasMoreTokens()) {
                    try {
                        String line = br.readLine();
                        if (line == null) return false;
                        st = new StringTokenizer(line);
                    } catch (IOException e) {
                        return false;
                    }
                }
                return true;
            }

            @Override
            public String next() {
                return st.nextToken();
            }
        };

        // 读取核心参数：n, m, s, e, a, b
        int n = Integer.parseInt(tokenIter.next());
        int m = Integer.parseInt(tokenIter.next());
        int s = Integer.parseInt(tokenIter.next());
        int e = Integer.parseInt(tokenIter.next());
        int a = Intege