yukicoder No.134 走れ！サブロー君

問題

問題概要

巡回セールスマン問題に辺のコストを加えたもの。

解法

巡回セールスマン問題ですね。bitDPで解きました。ただ今回の問題は、荷物をどれだけ持っているかで、1単位を移動するのにかかる時間が異なるので、それを前計算で、weight[mask] := mask集合を訪れた時に荷物の合計値を計算しておく。あとは、ddp[mask][i] := mask集合を巡って、iにいるときの最小コスト　としてループで回して計算していく。
答えは、dp[(1 << (n + 1)) - 1][0]と、荷物を下すのにかかる時間(w1からw2の合計)である。荷物を下すのにかかる時間はどのような順番で街を回っても、変化はしない。

ミス

典型?

コード

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int x[20], y[20];
double w[20];
int dist[20][20];
//dp[mask][i] := mask集合を巡って、iにいるときの最小コスト
double dp[(1 << 20)][20];
//weight[maks] := mask集合の時の荷物の重さ
double weight[(1 << 20)];

int main(void){
    cin >> x[0] >> y[0];
    w[0] = 0.0;
    int n; cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> x[i] >> y[i] >> w[i];
    }

    rep(i, n + 1)rep(j, n + 1){
        int len = abs(x[i] - x[j]) + abs(y[i] - y[j]);
        dist[i][j] = len;
    }

    //前計算
    for (int mask = 0; mask < (1 << (n + 1)); ++mask)
    {
        double tmp = 0;
        for (int i = 0; i < n + 1; ++i)
        {
            if((mask & (1 << i)) == 0){
                tmp += w[i];
            }
        }
        weight[mask] = tmp;
    }

    rep(i, (1 << 20))rep(j, 20) dp[i][j] = INF;
    dp[0][0] = 0;
    for (int mask = 0; mask < (1 << (n + 1)); ++mask)
    {
        for (int i = 0; i < n + 1; ++i)//現在時点
        {
            for (int p = 0; p < n + 1; ++p)//次に行くところ
            {
                if((mask & (1 << p)) == 0){//pをまだ訪れていない
                    //mask集合を訪れた後に、iからpに向かうときにかかるコスト
                    double cost = dist[i][p] * (double)((weight[mask] + 100.0) / 120.0);
                    dp[mask | (1 << p)][p] = min(dp[mask | (1 << p)][p], dp[mask][i] + cost);
                }
            }
        }
    }
    double ret = 0;
    for (int i = 0; i < n + 1; ++i){
        ret += w[i];
    }
    printf("%.9f\n", dp[(1 << (n + 1)) - 1][0] + ret);
    return 0;
}