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; }