3
0 2 1
1 0 2
2 1 0
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

3
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

4
0 2 1 3
1 0 2 5
2 1 0 4
3 2 6 0
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

8
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

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))

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62

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;
    }
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">