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