一、 题目理解

1. 基本概念

   • Hamilton路径：从起点到终点 不重复 地经过所有点 恰好一次 的路径
   • 要求从点0到点n-1的 最短 Hamilton路径长度

2. 题目条件
   a[x,x] = 0 // 自己到自己的距离为0
   a[x,y] = a[y,x] // 无向图（距离具有对称性）
   a[x,y] + a[y,z] ≥ a[x,z] 满足三角不等式：保证了通过其他点绕路不会得到更短的距离

二、解题思路

1. 状态定义

dp[state][u]  
// state: 表示已经访问过的点的集合（用二进制表示）
// u: 表示当前所在的点
 ** dp[state][u]: 表示从起点0出发，经过state中的点，当前在点u的最短路径长度 **

1. 状态转移方程

dp[state][u] = min(dp[state - {u}][v] + a[v][u])
// v是state中除u以外的任意点

从起点0开始到v点再到终点u的过程，由于v点 –> u点距离是确定的，只能改变的是起点到v点的距离，dp[state - {u}][v]就是除去u点以外的任意点到v点的距离

三、 代码

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int N = 20, INF = 0x3f3f3f3f;

int n;
int a[N][N];
/* dp[state][u]: 表示从起点0出发，经过state中的点，当前在点u的最短路径长度;
          state: 表示已经访问过的点的集合（用二进制表示）
*/
int dp[1 << N][N];

int solve() {
    // 读入n和距离矩阵
    cin >> n;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }

    // 初始化dp数组
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0;  // 初始状态：只访问了起点0

    // 枚举所有状态
    for(int state = 1; state < (1 << n); state++) {
        // 如果起点0不在state中，跳过
        if(!(state & 1)) continue;

        // 枚举当前所在的点u
        for(int u = 0; u < n; u++) {
            // 如果u不在state中，跳过
            if(!(state & (1 << u))) continue;

            // 枚举上一个点v
            for(int v = 0; v < n; v++) {
                // 如果v不在state中或v等于u，跳过
                if(!(state & (1 << v)) || v == u) continue;

                // 状态转移方程
                dp[state][u] = min(dp[state][u], dp[state ^ (1 << u)][v] + a[v][u]);
            }
        }
    }

    // 返回最终结果
    return dp[(1 << n) - 1][n - 1];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout << solve() << endl;
    return 0;
}