AOJ 2254 Fastest Route
最短ルート
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2254
問題概要
16個くらいのステージがある。
そのときの装備品によって、ステージの攻略の早さが変わる。
装備品はそれぞれのステージをクリアすると手に入る。
全ステージを最短でクリアするのはどうすればよいか。
解法
bitDP
ソース
#include<iostream> #define REP(i,b,n) for(int i=b;i<(int)n;i++) #define rep(i,n) REP(i,0,n) using namespace std; const int INF = 1000000000; int main(){ int n; while(cin >> n){ if(n == 0)break; int dp[(1 << n)], t[n][n+1]; rep(i, n){ rep(j, n+1){ cin >> t[i][j]; } } rep(i, (1<<n)){ dp[i] = INF; } dp[0] = 0; rep(i, (1<<n)){ rep(stage, n){ if((i & (1<<stage))!= 0)continue; dp[i + (1<<stage)] = min(dp[i] + t[stage][0], dp[i+(1<<stage)]); rep(tool, n){ if((i & (1 << tool)) == 0)continue; dp[i + (1<<stage)] = min(dp[i] + t[stage][tool+1], dp[i+(1<<stage)]); } } } cout << dp[(1<<n)-1] << endl; } return 0; }