roiti46's blog

主に競プロ問題の解説を載せてます

AOJ 2254: Fastest Road

DP苦手なので(とくに自力で解けなかった)DP問題は積極的に記事にしていこうと思う。

問題

問題はこちら

N個のダンジョンをクリアしていきたい。 あるダンジョンiをクリアするのに、ダンジョンjをクリア済みならt_ijという時間でクリアすることができる。 どのダンジョンもクリアしていないのならt_i0という時間でクリアできる。(ダンジョン番号は1-indexed) N x (N+1)のt_ijの値が与えられるから、すべてのダンジョンをクリアするのにかかる時間を答える。 N <= 16で、データセット複数個ある。

解法

N個の頂点の周り方についてなので、いわゆる巡回セールスマン問題の派生で、BitDPで解ける。 はじめ、蟻本の都市0からスタートしたときの巡回セールスマン問題の解法を写して、すべてのスタート位置から始めたときの最小値を取っていた。しかし、この方法だと最大226 163 で制限の8secに間に合わなかった(14secぐらいかかった)。

今回ダンジョンのはじめにクリアするダンジョン(スタート位置)は任意なので、各ゲーム状態(つまりbit)からクリアしていないダンジョンについてクリアコストを求め、クリア後のゲーム状態について最小値をとっていけばいいことになる。

#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#define REP(i,a,b) for (int i = (a); i < (b); i++)
#define rep(i,a) REP(i,0,a)
using namespace std;

const int INF = 1 << 28;

int N;
int t[16][17], dp[1 << 16];

int main(void){
    while (cin >> N && N) {
        rep(i, N) rep(j, N + 1) cin >> t[i][j];

        rep(i, 1 << N) dp[i] = INF;
        dp[0] = 0;
        rep(bit, 1 << N) {
            rep(i, N) {
                if (bit & 1 << i) continue;
                int cost = t[i][0];
                rep(j, N) if (!(bit & 1 << j) && i != j) cost = min(cost, t[i][j+1]);
                int now = bit | 1 << i;
                dp[now] = min(dp[now], dp[bit] + cost);
            }
        }
        cout << dp[(1 << N) - 1] << endl;
    }
    return 0;
}

巡回セールスマン問題はスタート都市が指定されていない方が簡単に解けるということがわかった。DPは例外がない方が解きやすいということか。

ちなみにダメだったコードが以下になる。

#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#define REP(i,a,b) for (int i = (a); i < (b); i++)
#define rep(i,a) REP(i,0,a)
using namespace std;
const int INF = 1 << 28;

int sp, N;
int t[16][17], dp[1 << 16][16], cost[1 << 16][16];

int rec(int S, int v) {
    if (dp[S][v] > 0) return dp[S][v];
    if (S == (1 << N) - 1 && v == sp) return dp[S][v] = 0;

    int res = INF;
    rep (u, N) {
        if (!(S >> u & 1)) {
            res = min(res, rec(S | 1 << u, u) + cost[S][u]);
        }
    }
    return dp[S][v] = res;
}

int main(void){
    while (1) {
        cin >> N;
        if (N == 0) break;
        rep(i, N) rep(j, N + 1) cin >> t[i][j];
        rep(u, N) rep(S, 1 << N) {
            int tmp = t[u][0];
            rep(k, N) if (S & 1 << k) tmp = min(tmp, t[u][k + 1]);
            cost[S][u] = tmp;
        }
        
        int ans = INF;
        for (sp = 0; sp < N; sp++) {
            memset(dp, -1, sizeof(dp));
            ans = min(ans, rec(0, sp));
        }
        cout << ans << endl;
    }
    return 0;
}