题目描述

使用二进制数来压缩状态
假设有n个节点，那么就可以使用一个n位的二进制数字来表示所有的状态，每一位代表一个节点，然后这一位为1表示节点被选择，这一位为0表示没有选择。
f[i][j] ，中j表示当前节点，i表示以j为终节点的路径代表的二进制数字，f[n][j]则表示以j为目的节点的所有路径（二进制数字从0到最大值）

然后就是图论中的思想了
在求f[i][j]得时候，需要遍历所有路径中包含节点j得路径（(i >> j) & 1），然后进行路径压缩
找到所有以j为终点得路径之后，再遍历从0到j的所有中间节点，尝试对其进行路径压缩，最后求出来的就是最小值

C++ 代码

 #include <iostream>
 #include <cstring>
 #include <limits.h>
 using namespace std;
 const int N = 20 , M = 1 << N;
 int w[N][N];
 int f[M][N];
 int main(){
     memset(f , 0x3f , sizeof f);
     f[1][0] = 0;
     int n ;
     cin >> n;
     for(int i = 0;i < n;++i)
        for(int j = 0;j < n;++j)
            cin >> w[i][j];
    for(int i = 0;i < 1 << n;++i){
        for(int j = 0;j < n;++j){
            if(i >> j & 1){
                for(int k = 0;k < n;++k){
                    if((i - (1 << j)) >> k & 1){
                        f[i][j] = min(f[i][j] , f[i - (1 << j)][k] + w[k][j]);
                    }
                }
            }
        }
    }
    cout << f[(1 << n) - 1][n -1 ] << endl;
    return 0;
 }