結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
![]() |
提出日時 | 2024-11-08 21:40:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 125 ms / 2,000 ms |
コード長 | 1,060 bytes |
コンパイル時間 | 820 ms |
コンパイル使用メモリ | 73,208 KB |
実行使用メモリ | 61,440 KB |
最終ジャッジ日時 | 2024-11-08 21:41:12 |
合計ジャッジ時間 | 4,125 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <iostream>#include <algorithm>#include <cmath>#include <cstdio>#define rep(i, n) for(i = 0; i < n; i++)#define int long longusing namespace std;void chmin(double &a, double b) { a = min(a, b); }int INF = 1e+18;int n, K;int x[15], y[15];double dp[1 << 15][15][15];double dist(int a, int b) {double dx = x[a] - x[b];double dy = y[a] - y[b];return sqrt(dx * dx + dy * dy);}signed main() {int i, j, k, l;cin >> n >> K;rep(i, n) cin >> x[i + 1] >> y[i + 1];n += 1;rep(i, (1 << n)) rep(j, n) rep(k, K + 1) dp[i][j][k] = INF;dp[1][0][K] = 0;rep(i, (1 << n)) {rep(j, n) {rep(k, K + 1) {if (dp[i][j][k] >= INF) continue;rep(l, n) {if ((i >> l) % 2) continue;if (k > 0) {chmin(dp[i + (1 << l)][l][k - 1], dp[i][j][k] + dist(j, l));}chmin(dp[i + (1 << l)][l][K - 1], dp[i][j][k] + dist(j, 0) + dist(0, l));}}}}double ans = INF;rep(i, n) {rep(j, K + 1) {chmin(ans, dp[(1 << n) - 1][i][j] + dist(i, 0));}}printf("%.14f\n", ans);return 0;}