华为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);
}
}