結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
![]() |
提出日時 | 2024-11-08 22:08:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 885 ms / 2,000 ms |
コード長 | 1,362 bytes |
コンパイル時間 | 217 ms |
コンパイル使用メモリ | 82,248 KB |
実行使用メモリ | 135,464 KB |
最終ジャッジ日時 | 2024-11-08 22:09:06 |
合計ジャッジ時間 | 15,497 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
N, K = map(int, input().split())place = [list(map(int, input().split())) for _ in range(N)]def distance(x1, y1, x2, y2):return ((x2-x1)**2 + (y2-y1)**2) ** 0.5dist = [[0]*N for _ in range(N)]for i in range(N):x1, y1 = place[i]for j in range(N):x2, y2 = place[j]dist[i][j] = distance(x1, y1, x2, y2)dist2 = [[0]*N for _ in range(N)]for i in range(N):x1, y1 = place[i]for j in range(N):x2, y2 = place[j]dist2[i][j] = distance(x1, y1, 0, 0)+distance(0, 0, x2, y2)# dp[i][j][k] i:現在地 j:持っているプレゼントの数 k:既に届けた場所の集合INF = 10**18dp = [[[INF]*(1<<N) for _ in range(K)] for _ in range(N)]for i in range(N):x, y = place[i]dp[i][K-1][1<<i] = distance(0, 0, x, y)for bit in range(1<<N):for i in range(N):for j in range(K):if dp[i][j][bit] == INF:continuefor k in range(N):if not 1<<k & bit:if 1 <= j:dp[k][j-1][bit|1<<k] = min(dp[k][j-1][bit|1<<k], dp[i][j][bit]+dist[i][k])dp[k][K-1][bit|1<<k] = min(dp[k][K-1][bit|1<<k], dp[i][j][bit]+dist2[i][k])ans = 10**18for i in range(N):x, y = place[i]for j in range(K):ans = min(ans, dp[i][j][(1<<N)-1]+distance(x, y, 0, 0))print(ans)