結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
![]() |
提出日時 | 2024-11-10 02:44:11 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 180 ms / 2,000 ms |
コード長 | 1,346 bytes |
コンパイル時間 | 3,942 ms |
コンパイル使用メモリ | 209,320 KB |
実行使用メモリ | 71,296 KB |
最終ジャッジ日時 | 2024-11-10 02:44:19 |
合計ジャッジ時間 | 6,316 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>//#include <atcoder/modint>using namespace std;//using namespace atcoder;using ld = long double;//using mint = modint998244353;int main(){cin.tie(nullptr);ios_base::sync_with_stdio(false);/*dp(S, i, j) = 訪れた店の集合がSで現在iにいてj枚ピザをもっている状態での最小値*/int N, K, M;ld d;cin >> N >> K;vector<ld> x(N+1), y(N+1);for (int i=0; i<N; i++) cin >> x[i] >> y[i];auto dist=[&](int i, int j)->ld{return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));};M = 1<<N;vector dp(M, vector(N+1, vector<ld>(K+1, 1e18)));dp[0][N][K] = 0;for (int i=0; i<M; i++){for (int j=0; j<=N; j++){for (int k=0; k<=K; k++){if (dp[i][j][k] == 1e18) continue;//ピザ屋dp[i][N][K] = min(dp[i][N][K], dp[i][j][k]+dist(j, N));//家for (int l=0; l<N; l++){if (i>>l & 1) continue;if (k>=1) dp[i|(1<<l)][l][k-1] = min(dp[i|(1<<l)][l][k-1], dp[i][j][k] + dist(j, l));}}}}ld ans=1e18;for (int i=0; i<=K; i++) ans = min(ans, dp[M-1][N][i]);cout << setprecision(18) << ans << endl;return 0;}