結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
![]() |
提出日時 | 2024-11-13 11:45:40 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 23 ms / 2,000 ms |
コード長 | 1,279 bytes |
コンパイル時間 | 3,761 ms |
コンパイル使用メモリ | 276,744 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-13 11:45:46 |
合計ジャッジ時間 | 6,094 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>using namespace std;using i64 = long long;const int N = 14;int n, k, x[N], y[N];double dis[1 << N][N], d[1 << N], dp[1 << N];int t1(int x) {return x ? t1(x >> 1) + 1 : -1;}int ppc(int x) {return x ? ppc(x - (x & -x)) + 1 : 0;}double f(int x, int y) {return sqrt(x * (i64)x + y * (i64)y);}double f(int i) {return f(x[i], y[i]);}int main() {int n, k;cin >> n >> k;for(int i = 0; i < n; i ++)cin >> x[i] >> y[i];for(int i = 1; i < (1 << n); i ++) {fill(dis[i], dis[i] + n, 1e15);if(i == (i & -i))dis[i][t1(i)] = 2 * f(t1(i));else{for(int j = 0; j < n; j ++) {if(!((i >> j) & 1)) continue;for(int p = i ^ (1 << j), k = 0; k < n; k ++) {if((p >> k) & 1)dis[i][j] = min(dis[i][j], dis[p][k] - f(k) + f(j) + f(x[j] - x[k], y[j] - y[k]));}}}d[i] = *min_element(dis[i], dis[i] + n);if(ppc(i) > k) d[i] = 1e15;dp[i] = d[i];for(int j = i; j; j = (j - 1) & i)dp[i] = min(dp[i], dp[j] + d[i ^ j]);}cout << fixed << setprecision(7) << dp[(1 << n) - 1] << "\n";}