結果

問題 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]の結果のみ抽出  巡回箇所がK箇所を超えた場合はinfで上書き
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)] )
0