結果

問題 No.134 走れ！サブロー君
コンテスト
ユーザー ytft
提出日時 2021-03-15 11:11:46
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 10 ms / 5,000 ms
コード長 1,308 bytes
コンパイル時間 1,776 ms
コンパイル使用メモリ 173,588 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-06 23:59:06
合計ジャッジ時間 2,534 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

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


int main(){
    double inf=DBL_MAX;
    int N,x,y;
    double weight=0;
    double all;
    cin>>x>>y>>N;
    vector<int> X(N),Y(N);
    vector<double> W(N);
    for(int i=0;i<N;i++){
        cin>>X[i]>>Y[i]>>W[i];
        X[i]-=x;
        Y[i]-=y;
        weight+=W[i];
    }
    all=weight;
    double temp;
    vector<vector<double>> dp(N,vector<double>(1<<N,-1));
    for(int i=0;i<N;i++){
        dp[i][1<<i]=(weight+100)/120*(abs(X[i])+abs(Y[i]));
    }
    for(int j=0;j<(1<<N);j++){
        for(int i=0;i<N;i++){
            weight=0;
            for(int k=0;k<N;k++){
                if((j>>k)%2==0){
                    weight+=W[k];
                }
            }
            if((j>>i)%2==0){
                dp[i][j]=0;
            }else if(dp[i][j]==-1){
                temp=inf;
                for(int k=0;k<N;k++){
                    if(k!=i && (j>>k)%2==1){
                        temp=min(temp,dp[k][j-(1<<i)]+((weight+W[i]+100)/120)*(abs(X[i]-X[k])+abs(Y[i]-Y[k])));
                    }
                }
                dp[i][j]=temp;
            }
        }
    }
    temp=inf;
    for(int i=0;i<N;i++){
        temp=min(temp,dp[i][(1<<N)-1]+100*(abs(X[i])+abs(Y[i]))/120.0);
    }
    cout<<fixed<<setprecision(8)<<temp+all<<endl;
}
0