ICPC練習会2011 Problem.C 最短ルート

ステージをクリアすると装備品がもらえる。装備品によって、ステージのクリア時間が変わる。
今持っている装備品を状態として、メモ化再帰して解いてみた。

最小全域有向木を使うともっと早いらしい。
http://www.prefield.com/algorithm/graph/chu_liu_edmonds.html
本番で実装無理><

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

const int INF = 1<<20;

int n;
int t[20][20];
int dp[1<<17];

int b(int s, int i) {
	int dt = t[i+1][0];
	for(int j=0;j<n;j++) {
		if(s&(1<<j)) dt = min(dt, t[i+1][j+1]);
	}
	return dt;
}

int a(int s) {
	int &dt = dp[s];
	if(dt<INF) return dt;

	for(int i=0;i<n;i++) {
		int ns = s & ~(1<<i);
		if(ns==s) continue;
		dt = min(dt, a(ns)+b(ns, i));
	}
	return dt;
}

int main() {
	while(true) {
		cin >> n;
		if(n==0) break;

		for(int i=1;i<=n;i++) {
			for(int j=0;j<=n;j++) {
				cin >> t[i][j];
			}
		}

		fill(dp, dp+sizeof(dp)/sizeof(int), INF);
		dp[0]=0;
		cout << a((1<<n)-1) << endl;
	}
	return 0;
}