結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
![]() |
提出日時 | 2024-11-08 23:18:55 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 257 ms / 2,000 ms |
コード長 | 2,951 bytes |
コンパイル時間 | 3,555 ms |
コンパイル使用メモリ | 256,808 KB |
実行使用メモリ | 139,008 KB |
最終ジャッジ日時 | 2024-11-08 23:19:04 |
合計ジャッジ時間 | 8,912 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; template <class T> using max_heap = priority_queue<T>; template <class T> using min_heap = priority_queue<T, vector<T>, greater<T>>; #define rep(i, l, r) for (ll i = (l); i < (r); i++) #define rrep(i, r, l) for (ll i = (r); i-- > (l);) #define all(x) begin(x), end(x) template <class T> bool chmin(T& lhs, T rhs) { return lhs > rhs ? (lhs = rhs, true) : false; } template <class T> bool chmax(T& lhs, T rhs) { return lhs < rhs ? (lhs = rhs, true) : false; } struct IOIO { IOIO() { cin.tie(0)->sync_with_stdio(0); } } ioio; template <class S, class T> ostream& operator<<(ostream& os, const pair<S, T>& p) { os << '(' << p.first << ", " << p.second << ')'; return os; } template <class T> ostream& operator<<(ostream& os, const vector<T>& vs) { os << '{'; rep(i, 0, (int)vs.size()) os << vs[i] << (i + 1 == (int)vs.size() ? "" : ", "); os << '}'; return os; } template <class T> ostream& operator<<(ostream& os, const set<T>& vs) { os << '{'; for (auto it = vs.begin(); it != vs.end(); it++) { if (it != vs.begin()) { os << ", "; } os << *it; } os << '}'; return os; } template <class T, class U> ostream& operator<<(ostream& os, const map<T, U>& vs) { os << '{'; for (auto it = vs.begin(); it != vs.end(); it++) { if (it != vs.begin()) { os << ", "; } os << *it; } os << '}'; return os; } #ifdef DEBUG void dump_func() { cerr << endl; } template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) { cerr << head; if (sizeof...(Tail) > 0) { cerr << ", "; } dump_func(std::move(tail)...); } #define dump(...) cerr << "[" + string(#__VA_ARGS__) + "] ", dump_func(__VA_ARGS__) #else #define dump(...) static_cast<int>(0) #endif void solve() { int n, K; cin >> n >> K; vector<pair<ld, ld>> p(n + 1); rep(i, 0, n) { ll x, y; cin >> x >> y; p[i] = {x, y}; } vector dist(n + 1, vector<ld>(n + 1)); rep(i, 0, n + 1) rep(j, 0, n + 1) { dist[i][j] = hypot(p[i].first - p[j].first, p[i].second - p[j].second); } const ld none = 1e18; vector dp(1 << (n + 1), vector(n + 1, vector<ld>(K + 1, none))); dp[1 << n][n][K] = 0; rep(i, 0, 1 << (n + 1)) rep(j, 0, n + 1) rep(k, 0, K + 1) { if (dp[i][j][k] == none) continue; rep(l, 0, n + 1) { if (l == n) { chmin(dp[i][l][K], dp[i][j][k] + dist[j][l]); } else if (k > 0 && (i & (1 << l)) == 0) { chmin(dp[i | (1 << l)][l][k - 1], dp[i][j][k] + dist[j][l]); } } } cout << fixed << setprecision(10); cout << dp[(1 << (n + 1)) - 1][n][K] << '\n'; } int main() { int t = 1; while (t--) solve(); }