結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
![]() |
提出日時 | 2024-11-09 02:59:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,043 ms / 2,000 ms |
コード長 | 1,979 bytes |
コンパイル時間 | 368 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 153,200 KB |
最終ジャッジ日時 | 2024-11-09 02:59:27 |
合計ジャッジ時間 | 20,017 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
from math import hypot, sqrtfrom functools import cachedef list3(a, b, c, *, val=0):return [[[val] * c for _ in range(b)] for _ in range(a)]@cachedef distance(a: tuple[int, int], b: tuple[int, int]) -> float:return hypot(a[0] - b[0], a[1] - b[1])def distance2(a, b) -> float:x1, y1 = (0, 0) if a == N else houses[a]x2, y2 = (0, 0) if b == N else houses[b]return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)INF = 1 << 60N, K = map(int, input().split())houses = []for _ in range(N):x, y = map(int, input().split())houses.append((x, y))dp = list3(1 << N, N, K, val=INF)# i : 訪問した頂点集合# j : 最後に訪れた頂点# k : 持っているピザの枚数# ときの時間の最小値# 初期状態for i, (x, y) in enumerate(houses):# d = distance((0, 0), (x, y))d = distance2(N, i)dp[1 << i][i][K-1] = dfor i in range(1 << N): # 訪れた頂点集合for j in range(N): # 最後に訪れた頂点if ~i & (1 << j): continuefor k in range(K): # 持っているピザの枚数if dp[i][j][k] == INF: continuefor to in range(N): # 次の訪問先if i & (1 << to): continueb = i | (1 << to)# cost = distance(houses[j], houses[to])cost = distance2(j, to)# 直接向かうif k > 0:dp[b][to][k-1] = min(dp[b][to][k-1], dp[i][j][k] + cost)# ピザ屋に戻ってから、次の家に向かう# cost2 = distance(houses[j], (0, 0)) + distance((0, 0), houses[to])cost2 = distance2(j, N) + distance2(N, to)dp[b][to][K-1] = min(dp[b][to][K-1], dp[i][j][k] + cost2)ans = INFb = (1 << N) - 1for j in range(N):for k in range(K):# d = dp[b][j][k] + distance(houses[j], (0, 0))d = dp[b][j][k] + distance2(j, N)ans = min(ans, d)print(ans)