結果
問題 | 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 secondusing 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 daufor (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];}