結果

問題 No.134 走れ！サブロー君
ユーザー 古寺いろは
提出日時 2015-04-04 16:33:55
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 6 ms / 5,000 ms
コード長 1,188 bytes
コンパイル時間 1,354 ms
コンパイル使用メモリ 162,144 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-14 17:14:12
合計ジャッジ時間 1,829 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include "bits/stdc++.h"
using namespace std;
double dp[1 << 13][13];
double INF = 1e100;
double hyp(double A, double B){
    return abs(A) + abs(B);
}
int main() {
    int X0, Y0;
    cin >> X0 >> Y0;
    int N;
    cin >> N;
    vector<int> X(N);
    vector<int> Y(N);
    vector<double> W(N);
    for (int i = 0; i < N; i++)
    {
        cin >> X[i] >> Y[i] >> W[i];
    }
    for (int i = 0; i < (1 << N); i++)
    {
        for (int j = 0; j < N; j++)
        {
            dp[i][j] = INF;
        }
    }
    double sumW = 0;
    for (int i = 0; i < N; i++)
    {
        sumW += W[i];
    }
    for (int i = 0; i < N; i++)
    {
        dp[(1 << N) - 1 - (1 << i)][i] = hyp(X0 - X[i], Y0 - Y[i]) * (sumW + 100) / 120;
    }
    for (int i = (1 << N) - 1; i >= 0; i--)
    {
        double SW = 100;
        for (int j = 0; j < N; j++)
        {
            if ((i >> j) % 2) SW += W[j];
        }
        for (int j = 0; j < N; j++)
        {
            if (dp[i][j] == INF) continue;
            for (int k = 0; k < N; k++)
            {
                if ((i >> k) % 2 == 0) continue;
                dp[i - (1 << k)][k] = min(dp[i - (1 << k)][k], dp[i][j] + hyp(X[j] - X[k], Y[j] - Y[k]) * SW / 120);
            }
        }
    }
    double ans = INF;
    for (int i = 0; i < N; i++)
    {
        ans = min(ans, dp[0][i] + (hyp(X0 - X[i], Y0 - Y[i]) * 100) / 120);
    }
    ans += sumW;
    printf("%.14f\n", ans);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0