记录编号	173524	评测结果	AAAAAAAAAA
题目名称	售货员的难题	最终得分	100
用户昵称	_Horizon	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2015-07-29 07:02:51	内存使用	2.31 MiB

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

#define maxn 16
using namespace std;

int dp[32768][16];
int a[maxn][maxn];
int n;
int main(){
	freopen("salesman.in","r",stdin);
	freopen("salesman.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	memset(dp,127,sizeof dp);
	dp[1][1]=0;
	for(int i=3;i<=(1<<n)-1;i+=2)
		for(int j=2;j<=n;j++)
			//当前状态为i，所在地点为j
			if(i&(1<<j-1)){
                int s=i^(1<<j-1);
				for(int k=1;k<=n;k++)
					if(k!=j&&(i&(1<<k-1)))
     					dp[i][j]=min(dp[i][j],dp[s][k]+a[k][j]);
			}
	int ans=0x7fffffff,S=(1<<n)-1;
	for(int i=1;i<=n;i++){
        dp[S][i]+=a[i][1];
        ans=min(ans,dp[S][i]);
	}
	printf("%d",ans);
	return 0;
}