結果

問題 No.2955 Pizza Delivery Plan
ユーザー Nguyễn Phúc Gia Nghi
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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];
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0