結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
![]() |
提出日時 | 2024-11-08 23:52:55 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 872 ms / 2,000 ms |
コード長 | 2,674 bytes |
コンパイル時間 | 3,487 ms |
コンパイル使用メモリ | 257,112 KB |
実行使用メモリ | 139,008 KB |
最終ジャッジ日時 | 2024-11-08 23:53:13 |
合計ジャッジ時間 | 17,124 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>#define For(i, a, b) for(int i = a; i < b; i++)#define rep(i, n) For(i, 0, n)#define rFor(i, a, b) for(int i = a; i >= b; i--)#define ALL(v) (v).begin(), (v).end()#define rALL(v) (v).rbegin(), (v).rend()using namespace std;using lint = long long;using ld = long double;int INF = 2000000000;lint LINF = 1000000000000000000;struct Point {ld x, y;};ld dist(Point a, Point b) {ld dx = a.x - b.x, dy = a.y - b.y;return sqrt(dx * dx + dy * dy);}int main() {int n, K;cin >> n >> K;n++;vector<Point> p(n);p[0] = {0.0, 0.0};For(i, 1, n) {cin >> p[i].x >> p[i].y;}vector<vector<vector<ld>>> dp(1 << n, vector<vector<ld>>(n, vector<ld>(K + 1, 1000000000000000000)));dp[1][0][K] = 0.0;rep(s, (1 << n)) {rFor(i, n - 1, 0) {rep(j, K + 1) {if (i == 0 && j != K) {continue;}rep(ni, n) {if (i == ni) {continue;}if (ni == 0) {ld d = dist(p[i], p[ni]);/*if (dp[s][0][K] > dp[s][i][j] + d) {cout << s << " " << i << " " << j << " -> " << s << " " << 0 << " " << K << endl;dp[s][0][K] = dp[s][i][j] + d;cout << dp[s][0][K] << endl;}*/dp[s][0][K] = min(dp[s][0][K], dp[s][i][j] + d);} else {if (s & (1 << ni) || j == 0) {continue;}int ns = s | (1 << ni);ld d = dist(p[i], p[ni]);/*if (dp[ns][ni][j - 1] > dp[s][i][j] + d) {cout << s << " " << i << " " << j << " -> " << ns << " " << ni << " " << j - 1 << endl;dp[ns][ni][j - 1] = dp[s][i][j] + d;cout << dp[ns][ni][j - 1] << endl;}*/dp[ns][ni][j - 1] = min(dp[ns][ni][j - 1], dp[s][i][j] + d);}}}}}/*rep(s, (1 << n)) rep(i, n) rep(j, K + 1) {if (dp[s][i][j] != 2000000000) {cout << s << " " << i << " " << j << " " << dp[s][i][j] << endl;}}*/ld ans = 1000000000000000000;rep(j, K + 1) {ans = min(ans, dp[(1 << n) - 1][0][j]);}cout << fixed << setprecision(10) << ans << endl;}