結果

問題 No.134 走れ！サブロー君
コンテスト
ユーザー maine_honzuki
提出日時 2020-05-19 18:38:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 23 ms / 5,000 ms
コード長 1,330 bytes
コンパイル時間 1,986 ms
コンパイル使用メモリ 171,872 KB
実行使用メモリ 7,808 KB
最終ジャッジ日時 2024-10-01 22:56:57
合計ジャッジ時間 2,310 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

double dp[1 << 15][15], w[1 << 15];

int main() {
    int X_0, Y_0, N;
    cin >> X_0 >> Y_0 >> N;
    vector<int> X(N + 2), Y(N + 2);
    vector<double> W(N + 2);
    double total = 0;
    for (int i = 1; i <= N; i++) {
        cin >> X[i] >> Y[i] >> W[i];
        X[i] -= X_0;
        Y[i] -= Y_0;
        total += W[i];
    }
    X[N + 1] = 0;
    Y[N + 1] = 0;


    auto t = [&](int i, int j, double w) {
        int dist = abs(X[i] - X[j]) + abs(Y[i] - Y[j]);
        return dist * (w + 100) / 120;
    };

    for (int bit = 0; bit < (1 << (N + 2)); bit++) {
        for (int i = 0; i < N + 2; i++) {
            dp[bit][i] = 1e30;
            if (bit & (1 << i))
                w[bit] += W[i];
        }
        w[bit] = total - w[bit];
    }
    dp[1][0] = 0;

    for (int bit = 0; bit < (1 << (N + 2)); bit++) {
        for (int i = 0; i < N + 2; i++) {
            if (bit & (1 << i)) {
                int mask = bit ^ (1 << i);
                for (int j = 0; j < N + 2; j++) {
                    if (mask & (1 << j)) {
                        dp[bit][i] = min(dp[bit][i], dp[mask][j] + t(j, i, w[mask]));
                    }
                }
            }
        }
    }

    cout << fixed << setprecision(10) << dp[(1 << (N + 2)) - 1][N + 1] + total << endl;
}
0