AOJ 0146 Lupin The 4th

問題

問題リンク

解法

訪れる順によって移動時間が変わる。一方、いままで訪れた蔵が同じであれば次に移動するときにかかる移動時間も同じである。

よって、今後どう移動するかはいままでの経路順によらないので、訪れた蔵の集合と現在地のみを状態として持てばよい。

これはbitDPで解くことができる。経路復元もやっておく。

メモ：順列を全探索したいときはbitDPが有効であることが多い。

Code

#include <bits/stdc++.h>
using namespace std;
 
int n, d[15], s[15], v[15], w[1<<15];
int pre[15][1<<15];  // 経路復元用の配列.直前に遷移した頂点番号を持つ.
double dp[15][1<<15];  // dp[現在地][すでに訪れたものの集合]
 
double t(int l, int S){
    return double(l)/(double(2000)/(70+w[S]*20));
}
 
double rec(int now, int S){
    if(dp[now][S] != -1) return dp[now][S];
    if(S == (1<<n)-1) return 0;
 
    double res = DBL_MAX;
    for(int i=0;i<n;i++){
        if((S>>i)&1) continue;
        double tmp = rec(i, S^(1<<i)) + t(abs(d[i]-d[now]), S);
        if(tmp < res){
            res = tmp;
            pre[now][S] = i;
        }
    }
    return dp[now][S] = res;
}
 
int main() {
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> s[i] >> d[i] >> v[i];
    }
    // 重さを前計算
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if((i>>j)&1){
                w[i] += v[j];
            }
        }
    }
    for(int i=0;i<n;i++) fill(dp[i], dp[i]+(1<<n), -1);
    int id = 0;
    double tmin = DBL_MAX;
    for(int i=0;i<n;i++){
        if(rec(i, 1<<i) < tmin){
            tmin = rec(i, 1<<i);
            id = i;
        }
    }
    cout << s[id];
    for(int S=1<<id; S<(1<<n)-1; S ^= 1<<id){
        id = pre[id][S];
        cout << " " << s[id];
    }
    cout << endl;
    return 0;
}