2317.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2317 on 2006-08-14 at 10:20:47 */ 
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int N = 14;

int bit[1<<N], cost[N][1<<N];

int main()
{
	int m[N][N], n, T, best[1<<N] = { 0 };
	
	scanf("%d", &T);
	for(int i = 0; i < N; i++) bit[1<<i] = i;
	for(int t = 1; t <= T; t++) {
		scanf("%d", &n);
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				scanf("%d", &m[i][j]);
		int w = 0, sn = 1 << n;
		for(int i = 0; i < n; i++) { w += m[i][i]; cost[i][0] = 0; }
		for(int i = 1; i < sn; i++) {
			best[i] = 1 << 30;
			for(int j = 0; j < n; j++) {
				int low = i&(-i), nst = i^low, st = i^(1<<j);
				cost[j][i] = cost[j][nst]+m[bit[low]][j];
				if(!(i&(1<<j))) continue;
				best[i] <?= cost[j][st]+best[st];
			}
		}
		printf("Scenario #%d:\nYou have officially been pimped for only $%d\n\n", t, w+best[sn-1]);
	}
	
	return 0;
}