結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
|
提出日時 | 2024-12-15 00:00:27 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 170 ms / 2,000 ms |
コード長 | 1,713 bytes |
コンパイル時間 | 1,891 ms |
コンパイル使用メモリ | 144,680 KB |
実行使用メモリ | 38,164 KB |
最終ジャッジ日時 | 2024-12-15 00:00:33 |
合計ジャッジ時間 | 6,125 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include<iostream>#include<string>#include<queue>#include<vector>#include<cassert>#include<random>#include<set>#include<map>#include<cassert>#include<unordered_map>#include<bitset>#include<numeric>#include<algorithm>using namespace std;using ll = long long;const int inf=1<<30;const ll INF=1LL<<62;typedef pair<ll,ll> P;typedef pair<int,P> PP;const ll MOD=998244353;const int dy[]={0,1,0,-1};const int dx[]={1,0,-1,0};void chmin(double &a,const double &b){a=min(a,b);}int main(){int N,K;cin>>N>>K;vector<P> pos(N+1);for(int i=0;i<N;i++){cin>>pos[i].first>>pos[i].second;}auto dist=[&](const P lhs,const P rhs)->double{double dx=lhs.first-rhs.first;double dy=lhs.second-rhs.second;return sqrt(dx*dx+dy*dy);};vector dp(1<<N,vector<vector<double>>(N,vector<double>(K+1,INF)));for(int i=0;i<N;i++){dp[1<<i][i][K-1]=dist({0,0},pos[i]);}for(int S=0;S<(1<<N);S++){for(int k=0;k<=K;k++){for(int now=0;now<N;now++){if(!(S>>now&1)) continue;for(int to=0;to<N;to++){if((S>>to)&1) continue;if(k-1>=0){chmin(dp[S|1<<to][to][k-1],dp[S][now][k]+dist(pos[now],pos[to]));}chmin(dp[S|1<<to][to][K-1],dp[S][now][k]+dist(pos[now],{0,0})+dist({0,0},pos[to]));}}}}double ans=INF;for(int t=0;t<=K;t++){for(int i=0;i<N;i++){//街iで終わるchmin(ans,dp[(1<<N)-1][i][t]+dist(pos[i],{0,0}));}}printf("%.10f\n",ans);}