记录编号	374128	评测结果	AAAAAAAAAA
题目名称	售货员的难题	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.791 s
提交时间	2017-02-22 15:09:56	内存使用	80.32 MiB

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>

using namespace std;

typedef long long LL;

void read(int &x) {
    char c;bool flag = 0;
    while((c=getchar())<'0'||c>'9') flag |= (c=='-');
    x=c-'0';while((c=getchar())>='0'&&c<='9') x = (x<<3)+(x<<1)+c-'0';
    flag?x=-x:x;
}
const int inf = 70746378;

int n,ans = inf;
int f[(1<<20)+10][20],dis[21][21];

int main() {
    freopen("salesman.in","r",stdin);freopen("salesman.out","w",stdout);
	memset(f,127/3,sizeof f);
	read(n);
	for (int i = 1; i <= n; i++)
	  for (int j = 1; j <= n; j++)
		read(dis[i][j]);
	f[1][1] = 0;
	for (int i = 1; i < (1<<n); i++)
	 for (int j = 1; j <= n; j++)
	  if(f[i][j] < inf)
	   for (int k = 1; k <= n; k++)
		 if(!(i&(1<<k-1)))
		   f[i|(1<<k-1)][k] = min(f[i|(1<<k-1)][k],f[i][j]+dis[j][k]);
	for (int i = 1; i <= n; i++)
	   ans = min(ans,f[(1<<n)-1][i]+dis[i][1]);
	printf("%d",ans);
	return 0;
}