結果

問題 No.2955 Pizza Delivery Plan
コンテスト
ユーザー haihamabossu
提出日時 2024-11-08 22:37:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 120 ms / 2,000 ms
コード長 1,302 bytes
コンパイル時間 2,401 ms
コンパイル使用メモリ 205,028 KB
最終ジャッジ日時 2025-02-25 02:56:28
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

const double INF = 1e18;
void solve() {
  ll n, k;
  cin >> n >> k;
  vector<ll> x(n), y(n);
  rep(i, n) cin >> x[i] >> y[i];
  auto dist = [&](ll sx, ll sy, ll tx, ll ty) -> double {
    ll dx = tx - sx, dy = ty - sy;
    return sqrt(double(dx * dx + dy * dy));
  };
  vector dp(1 << n, vector(n, vector<double>(k, INF + 10)));
  rep(i, n) dp[1 << i][i][k - 1] = dist(0, 0, x[i], y[i]);
  rep(S, 1 << n) rep(pi, n) rep(pk, k) if (dp[S][pi][pk] < INF) {
    rep(ni, n) if (((S >> ni) & 1) == 0) {
      ll T = S | (1 << ni);
      if (pk > 0) {
        double d = dist(x[pi], y[pi], x[ni], y[ni]);
        dp[T][ni][pk - 1] = min(dp[T][ni][pk - 1], dp[S][pi][pk] + d);
      }
      {
        double d = dist(x[pi], y[pi], 0, 0);
        d += dist(0, 0, x[ni], y[ni]);
        dp[T][ni][k - 1] = min(dp[T][ni][k - 1], dp[S][pi][pk] + d);
      }
    }
  }
  double ans = INF;
  rep(i, n) rep(ki, k) ans =
      min(ans, dp[(1 << n) - 1][i][ki] + dist(x[i], y[i], 0, 0));
  cout << fixed << setprecision(11) << ans << '\n';
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  int T = 1;
  for (int t = 0; t < T; t++) {
    solve();
  }
  return 0;
}
0