2421.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2421 on 2006-12-04 at 11:26:18 */
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int N = 11;
const int S = 1 << N;
const int INF = 1 << 20;
 
int map[N][N], opt[S][N], n;
 
int find(int, int);
 
int main()
{
	while(scanf("%d", &n) != EOF && n != 0) {
		n++;
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				scanf("%d", &map[i][j]);
		memset(opt, -1, sizeof(opt));
		int best = INF;
		for(int i = 1; i < n; i++) {
			int kt = find((1<<n)-1, i);
			best <?= kt+map[i][0];
			for(int j = 1; j < n; j++) best <?= kt+map[i][j]+map[j][0];
		}
		printf("%d\n", best);
	}
	
	return 0;
}
 
int find(int st, int k)
{
	if(opt[st][k] != -1) return opt[st][k];
	else if(!(st&(1<<k))) return INF;
	else if(st == (1<<k)) return (k == 0 ? 0 : INF);
	opt[st][k] = INF;
	for(int i = 0; i < n; i++) {
		if(!(st&(1<<i))) continue;
		opt[st][k] <?= min(find(st^(1<<k), i)+map[i][k], find(st^(1<<i), k)+map[i][k]+map[k][i]);
	}
	return opt[st][k];
}