//和最短Hamilton路径做法相同
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N = 22, M = 1<<20;
int n, m;
int f[M][N];
int w[N][N];
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=0; i<(1<<n); i++){
for(int j=0; j<n; j++){ //j表示当前城市
if(i >> j & 1){ //若状态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]);
}
}
}
}
}
//遍历当每个点为最终点时,计算从最后终点回到起点的最小值
int res = 1e9;
for(int i=0; i<n; i++){
res = min(res, f[(1<<n)-1][i]+w[i][0]);
}
cout<<res<<endl;
return 0;
}
blablabla