$\Huge\color{orchid}{点击此处获取更多干货}$

状态压缩+动态规划

这个问题由图论中的最短路问题衍生而来，但不同点有两处：
1. 必须不重不漏的经过每个节点
2. 经过节点的顺序一定会影响走过的距离

这样的话最短路部分的各算法就都不好使了，只能用DFS搜索每一条可能的路径，但是这样做也非常容易引起执行时间的爆炸式增长，因为时间复杂度是$O(n!)$级别的，那么还有没有优化的方式呢？

从寻找$\text{Hamilton}$路径的过程中来看，每往其中加入一个节点，无非就是记录了当前走到了哪个节点，以及有哪些节点已经走过了。在判断一个节点有没有走过的时候，一般会用到一个数组来记录，由于记录的都是0或1，因此这样的数组也可以用一个整数的二进制位来表示，其二进制第$i$位的1或0代表节点$i$已经走过或者没有走过，这就是该问题中对于状态信息的表示方法，而状态值的求解方式和最短路的松弛一致。直接给出dp表：

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int** val = new int*[n], ** dp = new int*[n];
    for (int i = 0; i < n; i++) {
        val[i] = new int[n];
        for (int j = 0; j < n; j++) {
            cin >> val[i][j];
        }
        dp[i] = new int[1 << n];
        fill(dp[i], dp[i] + (1 << n), INF);
    }

    dp[0][1] = 0;                                   //初始位于节点0，二进制第0位一定是1
    for (int cur = 1; cur < (1 << n); cur++)        //枚举经过节点的状态
    {
        for (int i = 0; i < n; i++)                 //枚举当前所在节点
        {
            if ((cur >> i) & 1)                     //所在的节点一定是经过了的，因此cur第i位必须要是1
            {
                for (int j = 0; j < n; j++)         //枚举前驱节点
                {
                    int pre = cur - (1 << i);       //前驱节点对应的状态中要把cur第i位的1抠了，再去判断第j位是不是1
                    if ((pre >> j) & 1) {           //开始转移
                        dp[i][cur] = min(dp[i][cur], dp[j][pre] + val[j][i]);
                    }
                }
            }
        }
    }
    cout << dp[n - 1][(1 << n) - 1] << endl;        //结束的状态就是位于节点n-1，并且经过了每一个节点（对应二进制n个1即(1<<n)-1）
    for(int i = 0; i < n; i++) {
        delete[] val[i], dp[i];
    }
    delete[] val, dp;
    return 0;
}