結果

問題 No.134 走れ！サブロー君
ユーザー なおなお
提出日時 2015-01-12 23:14:17
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 6 ms / 5,000 ms
コード長 2,005 bytes
コンパイル時間 1,494 ms
コンパイル使用メモリ 162,020 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-14 17:10:40
合計ジャッジ時間 2,009 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

// 想定解: bitDP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename _T> void rc(_T v,_T mn,_T mx){if(v<mn||mx<v){cerr<<"error"<<endl;exit(1);}}
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
#define FOR(i, f, t)        for(int(i)=(f);(i)<(t);(++i))
const int MINN = 1, MAXN = 13;
const int MINXY = 0, MAXXY = 1000;
const double MINW = 1, MAXW = 100;
const double EPS = 1e-7;

int N;
int Xbase, Ybase;

int X[MAXN+1], Y[MAXN+1];
double W[MAXN+1];
int dist[MAXN+1][MAXN+1];
const double INF = 1e9;

double Wsum[1<<MAXN];
double dp[MAXN][1<<MAXN]; // dp[最後に行った配達先][既に配達済みのビット] = 時間T

int main(){
    cin >> Xbase >> Ybase;
    cin >> N; rc(N, MINN, MAXN);

    REP(i,N){
        cin >> X[i] >> Y[i] >> W[i];
        rc(X[i], MINXY, MAXXY); rc(Y[i], MINXY, MAXXY); rc(W[i], MINW, MAXW);
    }

    // 重さの部分和生成
    Wsum[0] = 0;
    REP(i,N){
        REP(j,(1<<i)) Wsum[j+(1<<i)] = Wsum[j]+W[i];
    }

    // 配達先間の距離
    REP(i,N) REP(j,N){
        dist[i][j] = abs(X[i]-X[j]) + abs(Y[i]-Y[j]);
    }

    REP(i,N) REP(j,1<<N) dp[i][j] = INF;
    unsigned int fullbit = (1<<N)-1;

    // 最初の配達先の状態セット
    REP(i,N){
        int d = abs(X[i]-Xbase) + abs(Y[i]-Ybase);
        dp[i][1<<i] = d * (Wsum[fullbit] + 100) / 120.0 + W[i];
    }

    FOR(i,1,(1<<N)) REP(j,N){
        if((i & (1<<j)) == 0) continue;
        REP(k,N){   // 行き先
            if(i & (1<<k)) continue;
            int d = abs(X[k]-X[j]) + abs(Y[k]-Y[j]);
            double t = dp[j][i] + d * (Wsum[fullbit]-Wsum[i] + 100) / 120.0 + W[k];
            dp[k][i|(1<<k)] = min(dp[k][i|(1<<k)], t);
        }
    }

    // 最後に酒屋へ戻る時間を足して最小を出す
    double mint = INF;
    REP(i,N){
        int d = abs(X[i]-Xbase) + abs(Y[i]-Ybase);
        mint = min(mint, dp[i][fullbit] + d * (0 + 100) / 120.0);
    }
    cout << fixed << setprecision(9) << mint << endl;

}
0