結果

問題 No.134 走れ！サブロー君
ユーザー maine_honzukimaine_honzuki
提出日時 2020-05-19 18:38:51
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 21 ms / 5,000 ms
コード長 1,330 bytes
コンパイル時間 1,496 ms
コンパイル使用メモリ 169,268 KB
実行使用メモリ 7,780 KB
最終ジャッジ日時 2024-04-09 22:22:04
合計ジャッジ時間 2,239 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 4 ms
6,944 KB
testcase_06 AC 6 ms
6,944 KB
testcase_07 AC 12 ms
7,044 KB
testcase_08 AC 21 ms
7,780 KB
testcase_09 AC 21 ms
7,780 KB
testcase_10 AC 1 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 1 ms
6,940 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

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