結果
問題 |
No.2955 Pizza Delivery Plan
|
ユーザー |
|
提出日時 | 2025-01-29 21:45:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 147 ms / 2,000 ms |
コード長 | 1,459 bytes |
コンパイル時間 | 1,532 ms |
コンパイル使用メモリ | 163,680 KB |
実行使用メモリ | 106,308 KB |
最終ジャッジ日時 | 2025-01-29 21:46:03 |
合計ジャッジ時間 | 6,094 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> #define pii pair<double, double> #define fi first #define se second using namespace std; int n, k; pii points[20]; double dist[20][20], dp[1<<15][20][20]; double distance(pii x, pii y) { return sqrt((x.fi - y.fi)*(x.fi - y.fi) + (x.se - y.se)*(x.se - y.se)); } int main() { cin >> n >> k; for (int i=1; i<=n; i++) cin >> points[i].fi >> points[i].se; points[++n] = {0.0, 0.0}; // diem bat dau for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (i != j) dist[i][j] = distance(points[i], points[j]); for (int state = 0; state <= (1<<(n-1))-1; state++) for (int i=0; i<=n; i++) for (int j=0; j<=k; j++) dp[state][i][j] = 1e18; dp[0][n][k] = 0; for (int state = 0; state <= (1<<(n-1))-1; state++) for (int from = 1; from <= n; from++) if ((from == n) || ((state >> (from-1)) & 1)) { for (int remain = 1; remain <= k; remain++) for (int to = 1; to <= n; to++) if ((~state >> (to-1)) & 1) dp[state | (1<<(to-1))][to][remain-1] = min(dp[state | (1<<(to-1))][to][remain-1], dp[state][from][remain] + dist[from][to]); for (int remain = 0; remain <= k; remain++) dp[state][n][k] = min(dp[state][n][k], dp[state][from][remain] + dist[from][n]); } cout << fixed << setprecision(9) << dp[(1<<(n-1))-1][n][k]; }