結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
![]() |
提出日時 | 2024-11-09 19:54:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 871 ms / 2,000 ms |
コード長 | 829 bytes |
コンパイル時間 | 492 ms |
コンパイル使用メモリ | 82,580 KB |
実行使用メモリ | 139,524 KB |
最終ジャッジ日時 | 2024-11-09 19:54:42 |
合計ジャッジ時間 | 15,848 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
N,K=map(int, input().split())A=[(0,0)]D=[[0]*(N+1) for _ in range(N+1)]for i in range(N):x,y=map(int, input().split())A.append((x,y))for i in range(N+1):for j in range(N+1):x,y=A[i]xx,yy=A[j]D[i][j]=((x-xx)**2+(y-yy)**2)**.5dp=[[[10**18]*(1<<N) for _ in range(K+1)] for i in range(N+1)]from collections import dequed=deque()dp[0][K][0]=0for bit in range(1<<N):for k in range(0,K+1):for pre in range(N+1):if dp[pre][k][bit]==10**18:continuefor nex in range(1,N+1):nxt=nex-1if (bit>>nxt)&1==0:if k!=0:dp[nex][k-1][bit|(1<<nxt)]=min(dp[nex][k-1][bit|(1<<nxt)],dp[pre][k][bit]+D[pre][nex])dp[0][K][bit|(1<<nxt)]=min(dp[0][K][bit|(1<<nxt)],dp[pre][k][bit]+D[pre][nxt+1]+D[nex][0])c=dp[0][K][-1]print(c)