結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
|
提出日時 | 2024-11-08 22:07:18 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 1,116 bytes |
コンパイル時間 | 3,751 ms |
コンパイル使用メモリ | 253,900 KB |
実行使用メモリ | 12,800 KB |
最終ジャッジ日時 | 2024-11-08 22:07:25 |
合計ジャッジ時間 | 6,077 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include<bits/stdc++.h>using namespace std;#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#define int long longusing ld=long double;signed main(){int N,K;cin>>N>>K;vector<int> X(N+1),Y(N+1);for(int i=0;i<N;i++){cin>>X[i]>>Y[i];}X[N]=0,Y[N]=0;vector<vector<ld>> d(N+1,vector<ld>(N+1));for(int i=0;i<=N;i++){for(int j=0;j<=N;j++){d[i][j]=hypotl(X[i]-X[j],Y[i]-Y[j]);}}// cout<<"!"<<endl;vector<vector<ld>> dpdp(1<<(N+1),vector<ld>(N+1,1e18));dpdp[0][N]=0;for(int S=0;S<(1<<(N+1));S++){for(int i=0;i<=N;i++){for(int j=0;j<=N;j++){if(S>>j&1)continue;dpdp[S|(1<<j)][j]=min(dpdp[S|(1<<j)][j],dpdp[S][i]+d[i][j]);}}}// for(int S=0;S<(1<<(N+1));S++){// cout<<dpdp[S][N]<<" ";// }// cout<<endl;// cout<<"!"<<endl;vector<ld> dp(1<<N,1e18);dp[0]=0;for(int S=0;S<(1<<N);S++){int al=(1<<N)-1;int st=al^S;int sub=st;while(sub){if(__popcount(sub)<=K){dp[S|sub]=min(dp[S|sub],dp[S]+dpdp[sub|(1<<N)][N]);}sub=(sub-1)&st;}}cout<<fixed<<setprecision(20)<<dp[(1<<N)-1]<<endl;}