记录编号	214963	评测结果	AAAAAAAAAA
题目名称	售货员的难题	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.774 s
提交时间	2015-12-18 21:51:06	内存使用	80.29 MiB

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define AC_min(x, y) (x < y? x : y)
#define MAXN (20)

int dist[MAXN][MAXN];
int mem[MAXN][1<<MAXN];
int n;

int dp(int i, int s)
{
	int ans = 0x66666666;
	int k;
	if(mem[i][s] >= 0) return mem[i][s];
	if(s == 1) return dist[i][0];    //好吧，s == 1 
	else
	{
		for(k = 0; k < n; k++)
			if(s & (1 << k) && i != k)
				ans = AC_min(ans, dp(k, s ^ (1 << k)) + dist[i][k]);
	}	
	return mem[i][s] = ans;
}

void read_data()
{
	int i,j;
	scanf("%d", &n);
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			scanf("%d", &dist[i][j]);
	memset(mem, -1, sizeof(mem));	
}

void puts_res()
{
	printf("%d", dp(0, (1 << n) - 1));
}

void set_file()
{
	freopen("salesman.in", "r", stdin);
	freopen("salesman.out", "w", stdout);
}

int main()
{
	set_file(); 
	read_data();
	puts_res();		
	return 0;
}