結果

問題 No.134 走れ！サブロー君
コンテスト
ユーザー Yuki Inoue
提出日時 2023-12-24 01:34:15
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 10 ms / 5,000 ms
コード長 1,725 bytes
コンパイル時間 2,997 ms
コンパイル使用メモリ 247,768 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-27 13:32:11
合計ジャッジ時間 3,720 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int INF = 1e5;
ll MOD = 1e3;

int N, X, Y, x, y;
double w, o;

double distance(P p1, P p2){
    return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}

double tot_time(double distance, double tot_w, double w){
    return distance*(tot_w+100)/120 + w;
    
}

int main(){
    cin >> X >> Y;
    P start = make_pair(X,Y);

    cin >> N;

    double W[N];
    P d_points[N];
    rep(i,0,N){
        cin >> x >> y >> w;
        d_points[i] = make_pair(x,y);
        W[i] = w;
    }

    double tot_w[1<<N];
    tot_w[(1<<N)-1] = 0;
    rrep(i,(1<<N)-2,0) rep(j,0,N) if((i & (1<<j))==0){
        tot_w[i] = tot_w[i+(1<<j)] + W[j];
        break;
    }

    double dp[1<<N][N];
    rep(i,0,1<<N) rep(j,0,N) dp[i][j] = INF;
    rep(i,0,N) dp[1<<i][i] = tot_time(distance(start, d_points[i]), tot_w[0], W[i]);

    if(N==1){
        double ans = tot_time(distance(start, d_points[0]), tot_w[0], W[0]) + tot_time(distance(start, d_points[0]), 0, 0);
        printf("%.7f\n", ans);
        return 0;
    }

    rep(i,1,1<<N) rep(j,0,N) rep(k,0,N){
        if((i & (1<<k))==0 && (i & (1<<j))){
            o = dp[i][j] + tot_time(distance(d_points[j], d_points[k]), tot_w[i], W[k]);
            if(i + (1<<k) == (1<<N) - 1) dp[i+(1<<k)][k] = min(o + tot_time(distance(d_points[k], start), 0, 0), dp[i+(1<<k)][k]);
            else dp[i+(1<<k)][k] = min(o, dp[i+(1<<k)][k]); 
        }
    }

    double ans = *min_element(dp[(1<<N)-1], dp[(1<<N)-1]+N);
    printf("%.7f\n", ans);
}
0