状态表示：f[i][j]表示从0走到j，经过的路径状态是i的距离

集合划分：以倒数第二个点为依据，例如求到j的距离，先找到j的前一个点k，要求0->j，先求0->k的距离再加上k->j的距离

状态转移方程:f[i][j] = min(f[i][j] , f[i - (1 << j)][k] + w[j][k])

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 20 , M = 1 << N;

int n;
int w[N][N];
int f[M][N];//f[i][j]表示从0走到j，经过的状态是i的距离

int main()
{
    cin >> n;
    for(int i = 0 ; i < n ; i ++)
        for(int j = 0 ; j < n ; j++)
            cin >> w[i][j];

    memset(f , 0x3f , sizeof f);
    f[1][0] = 0;
    for(int i = 1 ; i < 1 << n ; i += 2)//因为起点是1，因此最低为必须要是1，因此步长设置为2
        for(int j = 0 ; j < n ; j++)
            if(i >> j & 1)//在i的状态下，可以到达点j
                for(int k = 0 ; k < n ; k++)
                    if(i >> k & 1)//在i的状态可以到达点k
                        f[i][j] = min(f[i][j] , f[i - (1 << j)][k] + w[j][k]);

    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}