結果

問題 No.2955 Pizza Delivery Plan
ユーザー navel_tos
提出日時 2025-01-11 14:40:00
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 649 ms / 2,000 ms
コード長 1,777 bytes
コンパイル時間 771 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 81,344 KB
最終ジャッジ日時 2025-01-11 14:40:30
合計ジャッジ時間 16,168 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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

#yukicoder 2955 Pizza Delivery Plan
#assert
N, K = map(int, input().split())
house = [tuple(map(int, input().split())) for _ in range(N)]
assert 1 <= K <= N <= 14
assert all( - 10 ** 9 <= Xi <= 10 ** 9 and - 10 ** 9 <= Yi <= 10 ** 9
for Xi, Yi in house )
assert all( house[i] != house[j] for i in range(N) for j in range(N) if i != j )
assert all( house[i] != (0, 0) for i in range(N) )
#Phase 1.
#sub[now][S]: now, S
# 1
dist = lambda Pi, Pj: sum( (Pi[k] - Pj[k]) ** 2 for k in range(2) ) ** 0.5
has_bit = lambda S, x: S >> x & 1
point = house + [(0, 0)]
n = len( point )
sub = [[1e18] * (1 << n) for _ in range(n)]
for i in range(n):
sub[i][1 << i] = dist( point[i], point[-1] )
for S in range(1 << n):
for now in range(n):
if has_bit(S, now) and sub[now][S] < 1e18:
for nxt in range(n):
if not has_bit(S, nxt):
sub[nxt][T] = min( sub[nxt][T := S | 1 << nxt],
sub[now][S] + dist( point[now], point[nxt] ) )
#sub[-1][S] Kinf
sub = [ sub[N][ S | 1 << N ] if S.bit_count() <= K else 1e18 for S in range(1 << N) ]
#Phase 2. DP
#DP[S]: S
DP = [1e18] * ( 1 << N )
DP[0] = 0.0
for S in range(1 << N):
T = S
while ( T := T - 1 ) >= 0:
DP[S] = min( DP[S], DP[ T := T & S ] + sub[ U := ~ T & S ] )
#
print( DP[~ (- 1 << N)] )
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0