結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
|
提出日時 | 2024-11-08 23:02:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,412 ms / 2,000 ms |
コード長 | 992 bytes |
コンパイル時間 | 468 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 140,124 KB |
最終ジャッジ日時 | 2024-11-08 23:03:07 |
合計ジャッジ時間 | 24,100 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
N,K=list(map(int,input().split()))M=[]def dist(i,j):return ((M[i][0]-M[j][0])**2+(M[i][1]-M[j][1])**2)**(0.5)for i in range(N):x,y=list(map(int,input().split()))M.append((x,y))M.append((0,0))dp=[]for i in range(N+1):p=[]for k in range(K+1):p.append([10**18]*(2**N))dp.append(p)dp[N][K][0]=0#dp[どこにいるかNならピザや][何枚あるか][どこ尋ねたか]for i in range(2**N):for j in range(N+1):for k in range(K+1):if dp[j][k][i]>10**15:continueif j!=N:if k==0:dp[N][K][i]=min(dp[N][K][i],dp[j][k][i]+dist(j,N))else:dp[N][K][i]=min(dp[N][K][i],dp[j][k][i]+dist(j,N))for l in range(N):if 2**j&i!=0 and 2**l&i==0:dp[l][k-1][i|2**l]=min(dp[l][k-1][i|2**l],dp[j][k][i]+dist(j,l))else:for l in range(N):if 2**l&i==0:dp[l][k-1][i|2**l]=min(dp[l][k-1][i|2**l],dp[j][k][i]+dist(j,l))print(dp[N][K][2**N-1])