結果

問題 No.134 走れ！サブロー君
ユーザー koyumeishi
提出日時 2015-01-30 20:54:45
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 12 ms / 5,000 ms
コード長 1,435 bytes
コンパイル時間 767 ms
コンパイル使用メモリ 82,928 KB
実行使用メモリ 5,888 KB
最終ジャッジ日時 2024-10-14 17:12:09
合計ジャッジ時間 1,452 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
double weight(vector<double> &w, int s){
    double ret = 0;
    for(int i=0; i<w.size(); i++){
        if((s>>i) & 1){
            ret += w[i];
        }
    }
    return ret;
}
double dfs(vector<vector<double>> &memo, vector<int> &x, vector<int> &y, vector<double> &w, int s, int pos){
    if(memo[s][pos] >= 0){
        return memo[s][pos];
    }
    int n = x.size()-1;
    double ret = 1e9;
    double w_ = weight(w, s|(1<<pos));
    for(int i=0; i<n; i++){
        if((s>>i) & 1) continue;
        if(i==pos) continue;
        int dist = abs(x[pos] - x[i]) + abs(y[pos] - y[i]);
        double t = (w_ + 100.0)/120.0 * dist + w[pos];
        double tmp = t + dfs(memo,x,y,w, s|(1<<pos), i);
        ret = min(ret, tmp);
    }
    memo[s][pos] = ret;
    return ret;
}
int main(){
    int x_,y_;
    cin >> x_ >> y_;
    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];
    }
    x.push_back(x_);
    y.push_back(y_);
    w.push_back(0);
    vector<vector<double>> dp(1<<(n+1), vector<double>(n+1, -1.0));
    double sum = weight(w, (1<<n)- 1 );
    for(int i=0; i<n; i++){
        int dist = abs(x_ - x[i]) + abs(y_ - y[i]);
        dp[ ((1<<(n+1))-1) ^ (1<<i) ][i] = (sum + 100.0)/120.0 * dist + w[i];
    }
    double ans = dfs(dp, x,y,w, 0, n);
    printf("%.11f\n", ans);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0