华为OD机试2024年真题（基站维修工程师）

基站维修工程师（200分）

小王是一名基站维护工程师，负责某区域的基站维护。
某地方有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到各站点的路程}

>>输出描述

最短路程的数值

>>示例1

输入

3
0 2 1
1 0 2
2 1 0

输出

3

思路： 

目标是解决典型的旅行商问题（TSP, Travelling Salesman Problem），即在一个给定的城市网络中，找到一条从起点城市出发，经过每个城市一次并最终返回起点的路径，使得路径的总距离最短。算法使用了递归（深度优先搜索）结合状态标记来遍历所有可能的路径，并通过回溯法不断比较最短路径。
输入：给定一个 size x size 的二维数组 arr，其中 arr[i][j] 表示城市 i 到城市 j 的距离。
输出：求解从城市0出发，经过每个城市一次并返回的最短路径长度。
 

步骤:
数据输入：读取城市数 size 和城市之间的距离矩阵 arr。
递归函数 recur：递归尝试从一个城市访问未访问过的下一个城市，记录当前路径长度，并使用状态数组 st 标记某个城市是否已经访问过。
状态回溯：递归探索完某条路径后，返回上一步，尝试其他未访问过的城市，最终比较得到最短路径。
结果输出：输出所有路径中的最小总距离。

代码段如下：

package com.rich.huawei.od_test;import java.util.Scanner;/*** @description* @Title Test01* @Author tang rui qi* @Date 2024/10/14 5:17*/
public class Test03 {static int res; // 用于保存最短路径的总距离// 递归函数// u: 当前访问的第几个城市// pre: 上一个访问的城市编号// temRes: 当前路径的总距离// size: 城市的总数// arr: 城市之间的距离矩阵// st: 访问状态数组，标记某个城市是否被访问过static void recur(int u, int pre, int temRes, int size, int[][] arr, boolean[] st) {// 如果已经访问完所有城市并回到起点城市if (u == size - 1) {// 将当前路径的总距离与最小距离进行比较，更新最小距离res = Math.min(res, temRes + arr[pre][0]);return;}// 遍历每个城市，寻找下一个未访问过的城市for (int i = 1; i < size; ++i) {if (st[i]) { // 如果该城市已被访问，则跳过continue;}st[i] = true; // 标记该城市为已访问// 递归访问下一个城市，并累加当前路径的距离recur(u + 1, i, temRes + arr[pre][i], size, arr, st);st[i] = false; // 回溯时将该城市重置为未访问状态}}public static void main(String[] args) {Scanner cin = new Scanner(System.in);int size = cin.nextInt(); // 读取城市的总数res = 0x3f3f3f3f; // 初始化最短路径为一个很大的值int[][] arr = new int[size][size]; // 城市之间的距离矩阵boolean[] st = new boolean[size]; // 访问状态数组// 读取距离矩阵的值for (int x = 0; x < size; ++x)for (int y = 0; y < size; ++y) arr[x][y] = cin.nextInt();// 从城市0开始递归搜索recur(0, 0, 0, size, arr, st);// 输出最短路径的总距离System.out.println(res);}}