分析

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

using namespace std;

const int N = 25;
int f[1 << 20][21]; 
int n;
int w[20][20];


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;// 只经过了点0

    for (int i = 1 ; i < 1 << n ; i ++ ) 
        for (int j = 0 ; j < n ; j ++) if (i >> j & 1) // 判断i的第j位是否为1
            for (int k = 0 ; k < n ; k ++ ) if (i >> k & 1) // 判读第i的第k位是否位1
                f[i][j] = min(f[i][j] , f[i ^ 1 << j][k] + w[k][j]); // 转移

    cout << f[(1 << n ) - 1][n - 1]; // 最终目标走到 (1 << n - 1) - 1这个状态，且点 n - 1 

    return 0;

}

作者：Global_zzz
链接：https://www.acwing.com/activity/content/code/content/542794/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。