AOJ 2254 Fastest Route http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2254&lang=jp ビットDP。いまいちわからん。

AOJ_2254.cpp

// start: 1:45
// AC: 2:34
#include <cmath>
#include <iostream>
#include <vector>

#define REP(i, n) for ( int i = 0; i < n; i++ )

using namespace std;

int main() {
    int n;
    
    while(cin >> n, n) {
        vector<vector<int> > inp(n, vector<int>(n+1, 0));

        REP(i, n) REP(t, n+1) cin >> inp[i][t];

        /**
        bdp[ステージフラグ|装備フラグ...] = 最短時間
        */

        vector<int> bdp(1<<n, 1<<29);

        bdp[0] = 0;

        REP(i, (1<<n)) {
            // 挑むステージ
            REP(to, n) {
                // 未クリアなら
                if ( (to & (1 << to)) == 0 ) {
                    int mint = inp[to][0];
                    // 使う装備
                    for ( int eq = 1; eq < n + 1; eq++ ) {
                        // このステージに使える装備があるとき
                        if ( (i & (1 << (eq-1))) > 0 ) mint = min(mint, inp[to][eq]);
                    }
                    bdp[i|(1<<to)] = min(bdp[i] + mint, bdp[i|(1<<to)]);
                    // cout << (1<<to) << " " << bdp[1<<to] << endl;
                }
            }
        }

        // 全フラグが立っている時
        cout << bdp[(1<<n)-1] << endl;
    }
    
    return 0;
}