結果

問題 No.134 走れ！サブロー君
ユーザー miwawawamiwawawa
提出日時 2024-08-15 22:54:26
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 12 ms / 5,000 ms
コード長 1,764 bytes
コンパイル時間 3,002 ms
コンパイル使用メモリ 251,532 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2024-08-15 22:54:30
合計ジャッジ時間 4,111 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
#include <cmath>
//#include <ranges>
using ll=long long;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define chmin(x,b) x=min(x,b)
using namespace std;
#define fi first
#define se second
using P=pair<int,int>;
using PD=pair<double,double>;
using PL=pair<ll,ll>;
int mod1=998244353;
int mod2=1000000007;
const ll INF = 1000000000000000000;
const int big = 2147483647;

struct st{
    ll x,y,z;
    st(ll x=0,ll y=0,ll z=0):x(x),y(y),z(z){}
    bool operator>(const st &a)const{
        return x>a.x;
    }
};
double dp[20010][20];
int main(){
    double n,q,y=0,i,z=0,x=0,d=0,k,L,nk,sum=0,T;
    ll ans=INF,sum2=0,rs=-1e9,cs=0,l=0,h=0,r=0,X;
    ll tmp2=0,flag=0,a=0,b=0,c=0,j=0,m=0,p,S,K;
    ll N,M=0,R;
    double sc,tc,w=0.0;
    cin>>sc>>tc;
    cin>>N;
    vector<PD>A;
    A.emplace_back(sc,tc);
    vector<double>cost;
    cost.push_back(0.0);
    rep(i,0,N){
        cin>>x>>y>>z;
        A.emplace_back(x,y);
        cost.push_back(z);
        w+=z;
    }
    rep(i,0,1<<(N+1))rep(j,0,N+1)dp[i][j]=1e18;
    double iju=1e18;
    auto cal=[](double ty)->double{return (ty+100.0)/120.0;};
    rep(i,1,N+1)dp[1<<i][i]=(double)cal(w)*(fabs(A[i].fi-sc)+fabs(A[i].se-tc))+(double)cost[i];
    rep(i,0,1<<(N+1)){
         double tmp=w;
        rep(j,0,N+1)if((i>>j)&1)tmp-=cost[j];
        rep(j,0,N+1){
            rep(k,0,N+1){
                if(!((i>>k)&1))continue;
                dp[i|(1<<j)][j]=min(dp[i|(1<<j)][j],dp[i][k]+(double)cost[j]+(double)cal(tmp)*(fabs(A[j].fi-A[k].fi)+fabs(A[j].se-A[k].se)));
            }

            if(i==(1<<(N+1))-1 && j==0){
                printf("%.10lf\n",dp[(1<<(N+1))-1][0]);
                return 0;
            }
        }
    }
    //cout<<cal(1)*1000<<endl;
    //cout<<iju<<endl;

    }
0