AOJ_2254

bitDPで解けた。
ビットの例…11001001　　　1,4,7,8のアイテム

#include <cstdio>
#include <algorithm>
using namespace std;

const int INF = 10000000;
const int MAX_N = 16;
const int MAX_C = 1 << MAX_N;
int table[MAX_N + 1][MAX_N + 1];//ステージnをアイテムmでクリアするときにかかる時間
int dp[MAX_C];
int N;
/*
bitDP
i = ビット表現でアイテムの種類
dp[i] := iで表されたアイテムすべてを手に入れるための最短時間

dp[0] := 0
dp[i] := min(dp[i & ~k] + table[kに対応するステージ番号][(j ∈  (i & ~k))に対応するアイテム番号]
         k,jは,iで立っているビットのうちの,一つのビットだけが立っている
*/
bool isbit(int b, int p){
	//bのp番目のビットがたっているか
	if(p == 0) return true;
	return ((b >> (p - 1)) & 1 == 1);
}
int solve(int n){
	dp[0] = 0;
	for(int i = 1; i < (1 << n); i++){
		dp[i] = INF;
		int k;
		for(int p = 1; p <= n; p++){
			if(isbit(i, p)){
				//iのp番目のビットが立っている
				k = 1 << (p - 1);
				for(int j = 0; j <= n; j++){
					if(isbit((i & ~k), j)){
						dp[i] = min(dp[i], dp[i & ~k] + table[p][j]);
					}
				}
			}
		}
	}
	return dp[(1 << n) - 1];
}
int main(){
	while(scanf("%d", &N)){
		if(N == 0) return 0;
		for(int i = 1; i <= N; i++){
			for(int j = 0; j <= N; j++){
				scanf("%d", &table[i][j]);
			}
		}
		printf("%d\n", solve(N));
	}
	return 0;
}