結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー | hirayuu_yc |
提出日時 | 2024-11-08 22:09:15 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 876 ms / 2,000 ms |
コード長 | 1,725 bytes |
コンパイル時間 | 3,351 ms |
コンパイル使用メモリ | 254,688 KB |
実行使用メモリ | 42,600 KB |
最終ジャッジ日時 | 2024-11-08 22:09:55 |
合計ジャッジ時間 | 17,981 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 3 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 | 35 ms
8,956 KB |
testcase_09 | AC | 35 ms
8,956 KB |
testcase_10 | AC | 116 ms
13,752 KB |
testcase_11 | AC | 256 ms
22,580 KB |
testcase_12 | AC | 348 ms
23,912 KB |
testcase_13 | AC | 489 ms
27,244 KB |
testcase_14 | AC | 558 ms
30,188 KB |
testcase_15 | AC | 688 ms
42,476 KB |
testcase_16 | AC | 847 ms
42,472 KB |
testcase_17 | AC | 823 ms
42,476 KB |
testcase_18 | AC | 855 ms
42,472 KB |
testcase_19 | AC | 846 ms
42,600 KB |
testcase_20 | AC | 856 ms
42,472 KB |
testcase_21 | AC | 818 ms
42,468 KB |
testcase_22 | AC | 823 ms
42,472 KB |
testcase_23 | AC | 859 ms
42,472 KB |
testcase_24 | AC | 824 ms
42,596 KB |
testcase_25 | AC | 345 ms
23,652 KB |
testcase_26 | AC | 253 ms
22,668 KB |
testcase_27 | AC | 116 ms
13,856 KB |
testcase_28 | AC | 876 ms
42,600 KB |
testcase_29 | AC | 840 ms
42,476 KB |
testcase_30 | AC | 875 ms
42,468 KB |
ソースコード
#include <iostream> #include <vector> #include <cmath> #include <unordered_map> #include <tuple> #include <limits> #include <map> #include<bits/stdc++.h> using namespace std; int N, K; vector<pair<double, double>> dot; // ユークリッド距離を計算する関数 double dist(const pair<double, double>& p, const pair<double, double>& q) { double x1 = p.first, y1 = p.second; double x2 = q.first, y2 = q.second; return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)); } // メモ化用のunordered_map unordered_map<int, double> memo; int mt(int x,int y ,int z){ return (x<<26)+(y<<17)+z; } // メモ化された再帰関数 double calc(int pizza, int pos, int bits) { if (memo.find(mt(pizza, pos, bits)) != memo.end()) { return memo[mt(pizza, pos, bits)]; } double ret; if (pizza == 0) { ret = calc(K, 0, bits) + dist(dot[0], dot[pos]); } else if (bits == ((1 << (N + 1)) - 1)) { ret = dist(dot[0], dot[pos]); } else { ret = numeric_limits<double>::max(); if (pizza != K) { ret = min(ret, calc(K, 0, bits) + dist(dot[0], dot[pos])); } for (int i = 1; i <= N; ++i) { if (!((bits >> i) & 1)) { double now = calc(pizza - 1, i, bits | (1 << i)) + dist(dot[i], dot[pos]); ret = min(ret, now); } } } memo[mt(pizza, pos, bits)] = ret; return ret; } int main() { cin >> N >> K; dot.emplace_back(0.0, 0.0); for (int i = 0; i < N; ++i) { double x, y; cin >> x >> y; dot.emplace_back(x, y); } std::cout << std::fixed << std::setprecision(16); cout << calc(K, 0, 1) << endl; return 0; }