結果

問題 No.2955 Pizza Delivery Plan
ユーザー haihamabossu
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0