結果
問題 | No.2955 Pizza Delivery Plan |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#yukicoder 2955 Pizza Delivery Plan#入力受取・assertN, K = map(int, input().split())house = [tuple(map(int, input().split())) for _ in range(N)]assert 1 <= K <= N <= 14assert all( - 10 ** 9 <= Xi <= 10 ** 9 and - 10 ** 9 <= Yi <= 10 ** 9for 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.5has_bit = lambda S, x: S >> x & 1point = 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.0for S in range(1 << N):T = Swhile ( T := T - 1 ) >= 0:DP[S] = min( DP[S], DP[ T := T & S ] + sub[ U := ~ T & S ] )#答えを出力print( DP[~ (- 1 << N)] )