結果

問題 No.2955 Pizza Delivery Plan
ユーザー haihamabossuhaihamabossu
提出日時 2024-11-08 22:37:27
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 101 ms / 2,000 ms
コード長 1,302 bytes
コンパイル時間 2,317 ms
コンパイル使用メモリ 211,352 KB
実行使用メモリ 38,272 KB
最終ジャッジ日時 2024-11-08 22:37:38
合計ジャッジ時間 4,939 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 34 ms
16,512 KB
testcase_09 AC 34 ms
16,768 KB
testcase_10 AC 48 ms
16,768 KB
testcase_11 AC 49 ms
16,512 KB
testcase_12 AC 56 ms
20,224 KB
testcase_13 AC 66 ms
20,096 KB
testcase_14 AC 74 ms
23,936 KB
testcase_15 AC 76 ms
23,808 KB
testcase_16 AC 92 ms
27,520 KB
testcase_17 AC 81 ms
27,392 KB
testcase_18 AC 87 ms
30,976 KB
testcase_19 AC 87 ms
30,848 KB
testcase_20 AC 91 ms
34,688 KB
testcase_21 AC 93 ms
34,560 KB
testcase_22 AC 96 ms
38,016 KB
testcase_23 AC 99 ms
38,272 KB
testcase_24 AC 98 ms
38,016 KB
testcase_25 AC 62 ms
20,096 KB
testcase_26 AC 50 ms
16,512 KB
testcase_27 AC 41 ms
16,768 KB
testcase_28 AC 90 ms
30,848 KB
testcase_29 AC 101 ms
30,848 KB
testcase_30 AC 97 ms
38,016 KB
権限があれば一括ダウンロードができます

ソースコード

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