結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
|
提出日時 | 2024-11-08 21:59:32 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,246 bytes |
コンパイル時間 | 3,089 ms |
コンパイル使用メモリ | 257,804 KB |
実行使用メモリ | 10,624 KB |
最終ジャッジ日時 | 2024-11-08 21:59:40 |
合計ジャッジ時間 | 6,785 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 TLE * 1 -- * 22 |
ソースコード
#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];}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]);}}X[N]=0,Y[N]=0;vector<ld> cost(1<<N);// cout<<"!"<<endl;for(int S=1;S<(1<<N);S++){vector<int> v={N};for(int i=0;i<N;i++){if(S>>i&1)v.push_back(i);}int n=v.size();vector<vector<ld>> dp(1<<n,vector<ld>(n,1e18));dp[0][0]=0;for(int s=0;s<(1<<n);s++){for(int j=0;j<n;j++){for(int k=0;k<n;k++){if(s>>k&1)continue;dp[s|(1<<k)][k]=min(dp[s|(1<<k)][k],dp[s][j]+d[v[j]][v[k]]);}}}cost[S]=dp[(1<<n)-1][0];// cout<<S<<" : "<<dp[(1<<n)-1][0]<<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]+cost[sub]);}sub=(sub-1)&st;}}cout<<fixed<<setprecision(20)<<dp[(1<<N)-1]<<endl;}