for(int i = 1;i<1<<20;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]);
现在的状态是一定经过了j,因为每个点只能经过一次 所以 j 是刚经过的,我们来看到达这个点是不是有其他的 k 点更近
}
}
}
}
}
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#define pb push_back
typedef long long ll;
using namespace std;
int w[20+5][20+5];
int f[1<<20][20];
int n ;
void work()
{
memset(f,0x3f,sizeof f);
f[1][0] = 0;
//cout << f[1][2];
for(int i = 1;i<1<<20;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];
}
int main()
{
// cout << 0x3f << endl;
//freopen("in.txt","r",stdin);
cin >> n;
for(int i = 0 ;i < n ;i ++){
for(int j = 0 ;j < n ;j++)
scanf("%d",&w[i][j]);
}
work();
return 0 ;
}