結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
|
提出日時 | 2024-11-08 22:37:27 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#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;}