結果

問題 No.2955 Pizza Delivery Plan
ユーザー norioc
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from math import hypot, sqrt
from functools import cache
def list3(a, b, c, *, val=0):
return [[[val] * c for _ in range(b)] for _ in range(a)]
@cache
def 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 << 60
N, 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] = d
for i in range(1 << N): #
for j in range(N): #
if ~i & (1 << j): continue
for k in range(K): #
if dp[i][j][k] == INF: continue
for to in range(N): #
if i & (1 << to): continue
b = 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 = INF
b = (1 << N) - 1
for 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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0