最短Hamilton路径

状态压缩dp

状态表示：dp[i][j]：第 i 种状态，目的地是 j 的最短距离。

这里的状态是指用一个二进制数的每个数位表示对应点是否经过，则一共有 $2^n$ 种状态，最终表示的状态为dp[(1 << n) - 1][n - 1]

状态计算：三层循环，第一层 i 枚举状态种类；第二层 j 枚举计算的终点；第三层 k 枚举到达 j 的上一个点，用到达 k 点的最短距离更新 j 点

状态转移方程：dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + v[k][j])

#include<bits/stdc++.h>
using namespace std;
const int N = 20, M = 1 << 20;

int n;
int dp[M][N], a[N][N];

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i ++){
        for(int j = 0; j < n; j ++){
            cin >> a[i][j];
        }
    }
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    for(int i = 0; i < 1 << n; i ++){
        for(int j = 0; j < n; j ++){
            if(i & 1 << j){
                for(int k = 0; k < n; k ++){
                    if(i & (1 << k))
                        dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + a[k][j]);
                }
            }
        }
    }
    cout << dp[(1 << n) - 1][n - 1] << '\n';
    return 0;
}