結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー | nono00 |
提出日時 | 2024-11-08 23:18:55 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 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 | 3 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 69 ms
39,040 KB |
testcase_09 | AC | 67 ms
39,168 KB |
testcase_10 | AC | 89 ms
46,720 KB |
testcase_11 | AC | 111 ms
54,528 KB |
testcase_12 | AC | 132 ms
62,208 KB |
testcase_13 | AC | 151 ms
69,760 KB |
testcase_14 | AC | 166 ms
77,440 KB |
testcase_15 | AC | 188 ms
84,992 KB |
testcase_16 | AC | 196 ms
92,800 KB |
testcase_17 | AC | 216 ms
100,480 KB |
testcase_18 | AC | 219 ms
108,416 KB |
testcase_19 | AC | 229 ms
115,968 KB |
testcase_20 | AC | 236 ms
123,648 KB |
testcase_21 | AC | 251 ms
131,328 KB |
testcase_22 | AC | 257 ms
139,008 KB |
testcase_23 | AC | 257 ms
138,880 KB |
testcase_24 | AC | 256 ms
138,880 KB |
testcase_25 | AC | 132 ms
62,208 KB |
testcase_26 | AC | 110 ms
54,400 KB |
testcase_27 | AC | 89 ms
46,720 KB |
testcase_28 | AC | 229 ms
108,288 KB |
testcase_29 | AC | 232 ms
115,968 KB |
testcase_30 | AC | 256 ms
138,880 KB |
ソースコード
#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(); }