```cpp
// luogu-judger-enable-o2
#include<cstdio>
using namespace std;
int w[21][21],f[21][21],ans=0xfffffff,a[21][21][21],n;
void first(int x){
for(int i=1;i<=x;++i)for(int j=1;j<=x;++j){
w[i][j]=0;f[i][j]=0x3f3f3f;
}
for(int i=1;i<=x;++i)
for(int j=1;j<=x;++j)
for(int k=1;k<=x;++k)
a[i][j][k]=0;
return;
}
int main(){
// freopen("salesman","r",stdin);
// freopen("salesman","w",stdout);
scanf("%d",&n);
first(n);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%d",&w[i][j]);
f[1][1]=w[1][1];
a[1][1][1]=1;
for(int i=2;i<=n;++i){
f[2][i]=w[1][i]+f[1][1];
a[2][i][1]=1;
a[2][i][i]=1;
}
for(int i=3;i<=n;++i)
for(int k=2;k<=n;++k){
int t=0;
for(int j=2;j<=n;++j)
if(j!=k) if(a[i-1][j][k]==0) if(f[i-1][j]+w[j][k]<f[i][k])
{
f[i][k]=f[i-1][j]+w[j][k];
t=j;
// for(int m=1;m<=n;++m)
// {
// if(a[i-1][j][m]==1) a[i][k][m]=1;
// }
// a[i][k][k]=1;
}
for(int j=1;j<=n;++j)
if(a[i-1][t][j]==1) a[i][k][j]=1;
a[i][k][k]=1;
}
for(int i=2;i<=n;++i)
if(f[n][i]+w[i][1]<ans) ans=f[n][i]+w[i][1];
printf("%d",ans);
return 0;
}
```
by xun0 @ 2018-03-11 09:09:54