当前位置：首页 > article >正文

【华为OD-E卷 - 基站维修工程师 100分（python、java、c++、js、c）】

article 2025/1/30 13:23:11

【华为OD-E卷 - 基站维修工程师 100分（python、java、c++、js、c）】

题目

小王是一名基站维护工程师，负责某区域的基站维护。
某地方有 n 个基站(1 < n < 10)，已知各基站之间的距离 s(0 < s < 500)，并且基站 x 到基站 y 的距离，与基站 y 到基站 x 的距离并不一定会相同。
小王从基站 1 出发，途经每个基站 1 次，然后返回基站 1 ，需要请你为他选择一条距离最短的路

输入描述

站点数n和各站点之间的距离(均为整数)，如：

3 {站点数} 0 2 1 {站点1到各站点的路程} 1 0 2 {站点2到各站点的路程} 2 1 0 {站点3到各站点的路程}

输出描述

最短路程的数值

用例

用例一：

输入：

输出：

用例二：

输入：

输出：

python解法

解题思路：

使用 find_paths 递归生成从点
0
0 出发、经过所有点的路径。
遍历生成的路径集合 paths，逐一计算路径的总距离。
在遍历过程中更新最小路径总距离。
返回最小距离作为最终结果。

import sys

# 读取输入
n = int(input())  # 点的数量
distances = [list(map(int, input().split())) for _ in range(n)]  # 距离矩阵

def min_path(distances, n):
    """
    计算从点 0 出发，遍历所有点的最小路径总距离。
    :param distances: 距离矩阵
    :param n: 点的数量
    :return: 最小路径总距离
    """
    # 存储所有可能的路径
    paths = []
    # 递归生成所有路径
    find_paths(n, [False] * n, [], paths)

    # 初始化最小距离为一个较大的值
    minimum = sys.maxsize

    # 遍历所有路径，计算每条路径的总距离
    for path in paths:
        # 初始从点 0 到路径中第一个点的距离
        total_distance = distances[0][path[0]]
        # 依次计算路径中点之间的距离
        for i in range(len(path) - 1):
            total_distance += distances[path[i]][path[i + 1]]
        # 回到点 0 的距离
        total_distance += distances[path[-1]][0]
        # 更新最小距离
        minimum = min(minimum, total_distance)

    return minimum

def find_paths(n, visited, current_path, paths):
    """
    使用递归生成从点 1 到点 n-1 的所有路径。
    :param n: 点的数量
    :param visited: 标记每个点是否已访问
    :param current_path: 当前正在生成的路径
    :param paths: 存储所有生成的路径
    """
    # 如果路径长度达到 n-1，记录当前路径
    if len(current_path) == n - 1:
        paths.append(current_path[:])  # 保存当前路径
        return

    # 遍历剩余的点，尝试加入路径
    for i in range(1, n):  # 从点 1 开始，点 0 作为起点不加入路径
        if not visited[i]:  # 如果当前点尚未访问
            current_path.append(i)  # 加入路径
            visited[i] = True  # 标记为已访问
            # 递归生成后续路径
            find_paths(n, visited, current_path, paths)
            # 回溯，撤销选择
            visited[i] = False
            current_path.pop()

# 输出最小路径总距离
print(min_path(distances, n))

java解法

解题思路

使用动态规划结合状态压缩来解决问题。
定义 dp[u][mask] 表示当前在点
𝑢
u，访问过的点集合为 mask 时的最短路径长度。
通过逐步扩展访问点的集合，从只访问起点
0
0 开始，逐步扩展到访问所有点。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 输入点的数量
        int n = sc.nextInt();
        
        // 输入距离矩阵
        int[][] dist = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = sc.nextInt();
            }
        }
        
        // 计算并输出最短路径
        System.out.println(tsp(dist, n));
    }

    /**
     * 使用动态规划求解 TSP 问题
     *
     * @param dist 距离矩阵
     * @param n    点的数量
     * @return     最短路径长度
     */
    public static int tsp(int[][] dist, int n) {
        // dp[u][mask]：当前在点 u，访问的点集合为 mask 时的最短路径长度
        int[][] dp = new int[n][1 << n];
        
        // 初始化 dp 表，所有值设置为无穷大
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < (1 << n); j++) {
                dp[i][j] = Integer.MAX_VALUE / 2; // 避免加法溢出
            }
        }
        
        // 初始状态：从点 0 出发，只访问点 0
        dp[0][1] = 0;

        // 枚举所有状态 mask
        for (int mask = 1; mask < (1 << n); mask++) {
            // 枚举当前点 u
            for (int u = 0; u < n; u++) {
                // 如果点 u 不在当前的点集合中，跳过
                if ((mask & (1 << u)) != 0) {
                    // 枚举下一个点 v
                    for (int v = 0; v < n; v++) {
                        // 如果点 v 已经访问过，跳过
                        if ((mask & (1 << v)) == 0) {
                            // 更新 dp[v][newMask]
                            dp[v][mask | (1 << v)] = Math.min(
                                dp[v][mask | (1 << v)], 
                                dp[u][mask] + dist[u][v]
                            );
                        }
                    }
                }
            }
        }

        // 计算结果：从终点返回起点的最短路径
        int result = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            result = Math.min(result, dp[i][(1 << n) - 1] + dist[i][0]);
        }
        return result;
    }
}