2023华为OD机试真题-基站维修工程师(JAVA、Python、C++)

题目描述：
小王是一名基站维护工程师，负责某区域的基站维护。
某地方有n个基站（1<n<10），已知各基站之间的距离s（0<s<500），并且基站x到基站y的距离，与基站y到基站x的距离并不一定会相同。
小王从基站1出发，途径每个基站1次，然后返回基站1，需要请你为他选择一条距离最短的路线。
输入描述：
站点数n和各站点之间的距离（均为整数）。如：
3 {站点数}
0 2  l  {站点1到各站点的路程}
1 0 2  {站点2到各站点的路程}
2 1 0  {站点3到各站点的路程} 

输出描述：
最短路程的数值
补充说明：
 收起
示例1
输入：
3
0 2 1
1 0 2
2 1 0
输出：
3
 

import java.util.*;
public class Main {
    static int min = 5000;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
 
        while (in.hasNext()) {// 注意，如果输入是多个测试用例，请通过while循环处理多个测试用例
            int a = in.nextInt();
            int[][] arr1 = new int[a][a];
            for (int i = 0; i < a; i++) {
                for (int j = 0; j < a; j++) {
                    arr1[i][j] = in.nextInt();
                }
            }
            int[] jizhan = new int[a];
            for (int i = 0; i < a; i++) {
                jizhan[i] = 1;
            }
            jisuan(arr1, jizhan, 0, 0, 0);
            System.out.println(min);
        }
 
 
    }
    static public void jisuan(int[][] arr1, int[] jizhan, int now, int bushu,
                              int sum) {
        if (bushu == jizhan.length - 1) {
            //System.out.println("sum:"+sum);
            //System.out.println(arr1[now][0]);
            sum = sum + arr1[now][0];
            //System.out.println("now:"+now);
            //System.out.println("sum:"+sum);
            min = Math.min(min, sum);
            return;
        }
        for (int i = 1; i < jizhan.length; i++) {
            if (jizhan[i] != 0) {
                jizhan[i] = 0;
                jisuan(arr1, jizhan, i, bushu + 1, sum + arr1[now][i]);
                jizhan[i] = 1;
            }
        }
    }
}

while True:
    try:
        m = int(input())
        lis = list()
        if m < 2:
            print(0)
            break
        for i in range(m):
            lis.append(list(map(int, input().strip().split())))
        dp = [[] * m for j in range(m)]
        a = 0
        while a < m:
            for i in range(m):
                dp[a].append(lis[i][a])
            a += 1
        res = 0
        for i in dp:
            num = sorted(i)
            res += num[1]
        print(res)
    except:
        break

#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
static    unordered_map<int,int> gRoad;   //!使用hash来表示当前路径是否走过
static     int         gMinWay;
static     int         gNum;
 
 
//! 检查当前基站是否已走过
static bool check(int x)
{
 //! 如果没找到表示还没走过
 if (gRoad.find(x) != gRoad.end())
 {
  return false;
 }
 
 return true;
}
//! 回溯
//! board: 棋盘
//! road : 基站，基站英文不会拼
//! way  : 距离，当前已走的距离  ps:有没有可能越界
static void backTracking(vector<vector<int>> &board,int road,int way)
{
 //! 终止条件
 if (gRoad.size() == gNum)
 {
  way += board[road][0];   //! 当前已走的路程加上最后返回的路程
  gMinWay = gMinWay < way? gMinWay: way;
  return;
 }
 
 for (int i = 0; i < gNum; i++)
 {
  //! 剪枝
  if (!check(i))
  {
   continue;
  }
  gRoad[i] = 0;   //! 值不重要，重要的是记录路径
  way      += board[road][i];
  //! 递归找下一个
  backTracking(board,i, way);
  //! 回溯
  gRoad.erase(i);
  way -= board[road][i];
 }
 
}
 
int main(void)
{
 int  tNum;      //! 基站个数
 
 cin >> tNum;   //! 拿到基站的个数
 
 vector<vector<int>> tBoard(tNum,vector<int>(tNum));  //! 初始化棋盘
 
 //! 初始化
 gNum    = tNum;
 gMinWay = 0x7FFFFFFF;   //! 默认初始路程为无穷大
 
 for (int i = 0; i < tNum; i++)
 {
  for (int j = 0; j < tNum; j++)
  {
   cin >> tBoard[i][j];
  }
 }
 
 //! 时间原因，采用回溯，希望不超时
 gRoad[0] = 0;    //! 将基站1，放到hash中去
 backTracking(tBoard,0,0);
 
 gRoad.clear();   //! 清空hash表，释放内存
 
 printf("%d", gMinWay);
 
 return 0;
}