题目描述

f[walked][node_i] 走到node_i时所有点的访问状态为walked(二进制模式)，访问过now即walked>>now&1 为真

细节见注释

#include<iostream>
#include<cstring>
using namespace std;

#define ffor(i,s,e) for(int i=s;i<e;i++)

const int N = 20;

int f[1<<20][N];
int w[N][N];

int main(){
    int n;
    cin>>n;
    ffor(i,0,n) ffor(j,0,n) scanf("%d", &w[i][j]);


    memset(f, 0x3f, sizeof f);
    f[1][0]=0;

    ffor(walked,0,1<<n){//遍历所有可能的路径
        ffor(now,0,n){//遍历可能走到的点
            if(walked>>now & 1){如果当前点走到了
                ffor(pre,0,n){
                    if(walked>>pre & 1){//对当前点的前驱做松弛操作
                         f[walked][now]=min(f[walked][now],f[walked-(1<<now)][pre]+w[pre][now]);
                    }
                }
            }
        }
    }

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


}