結果

問題 No.134 走れ！サブロー君
コンテスト
ユーザー Rumain831
提出日時 2026-08-25 18:34:27
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 9 ms / 5,000 ms
+ 480µs
コード長 929 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,484 ms
コンパイル使用メモリ 182,088 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2026-08-25 18:34:45
合計ジャッジ時間 2,729 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;
void chmin(double& a, double b){a=min(a, b);}

int main(void){
  ll x0, y0; cin >> x0 >> y0;
  int n; cin >> n;
  int mx=(1<<(n+1));
  vector<ll> x(n+1), y(n+1);
  vector<double> w(n+1);
  x[0]=x0, y[0]=y0;
  for(int i=1; i<=n; i++) cin >> x[i] >> y[i] >> w[i];
  vector dp(mx, vector<double>(n+1, 1e18));
  dp[1][0]=0;
  auto dist=[&](int s, int t){
    ll ans=abs(x[s]-x[t])+abs(y[s]-y[t]);
    return ans;
  };
  for(int i=1; i<mx; i++){
    double sw=0;
    for(int j=0; j<=n; j++)if(!(i>>j&1)) sw+=w[j];
    for(int st=0; st<=n; st++)if(i>>st&1){
      for(int to=0; to<=n; to++)if(!(i>>to&1)){
        chmin(dp[i|(1<<to)][to], dp[i][st]+(sw+100.0)/120.0*dist(st, to)+w[to]);
      }
    }
  }
  double ans=1e18;
  for(int i=1; i<=n; i++) chmin(ans, dp[mx-1][i]+dist(i, 0)*100/120.0);
  printf("%.10f\n", ans);
  return 0; 
}
0