记录编号	592854	评测结果	AAAAAAAAAA
题目名称	售货员的难题	最终得分	100
用户昵称	qyd	是否通过	通过
代码语言	C++	运行时间	0.622 s
提交时间	2024-08-02 15:43:24	内存使用	83.35 MiB

#include<bits/stdc++.h>
using namespace std;
const int maxn=20;
#define INF 0x3f3f3f3f
int n,ans,dist[maxn][maxn],f[1<<maxn][maxn];
//f[x][y] stands for the state x(to mark where he had been to)
//and y for the last(also the moment mow) dot he was in 
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){if(c=='-'){f*=-1;}c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void prework(){
	n=read();
	ans=INF;
	for(int i=0;i<n;i++)
	  for(int j=0;j<n;j++)
	    dist[i][j]=read();
	return ;
}
void dp(){
	memset(f,INF,sizeof(f));	
	f[1][0]=0;
	for(int i=1;i<(1<<n);i++){
		for(int j=0;j<n;j++){
			if(i&(1<<j)){
				for(int k=0;k<n;k++){
					if((i&(1<<k))&&k!=j){
						f[i][j]=min(f[i][j],f[i^(1<<j)][k]+dist[k][j]);
					}
				}
			}
		}
	}
	for(int i=0;i<n;i++){
		ans=min(ans,f[(1<<n)-1][i]+dist[i][0]);
	}
	return ;
}
void print(){
	cout<<ans<<endl;
	return ;
}
int main()
{
	freopen("salesman.in","r",stdin);
	freopen("salesman.out","w",stdout);
	prework();
	dp();
	print();
	return 0;
}