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