結果

問題 No.3158 Collect Stamps
ユーザー i_taku
提出日時 2025-05-27 14:46:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 211 ms / 2,000 ms
コード長 873 bytes
コンパイル時間 423 ms
コンパイル使用メモリ 82,196 KB
実行使用メモリ 76,372 KB
最終ジャッジ日時 2025-05-27 14:46:58
合計ジャッジ時間 4,322 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import permutations, combinations
from heapq import heappush, heappop


N, M, K = map(int, input().split())
A = [int(x) - 1 for x in input().split()]
T = [list(map(int, input().split())) for _ in range(N)]

dists = [[1 << 60] * N for _ in range(N)]
for i in range(N):
    dist = dists[i]
    dist[i] = 0
    hq = [(0, i)]
    while hq:
        d, u = heappop(hq)
        if d > dist[u]:
            continue
        for v, t in enumerate(T[u]):
            if dist[v] > d + t:
                dist[v] = d + t
                heappush(hq, (dist[v], v))

ans = 1 << 60
for comb in combinations(range(N), M):
    for perm in permutations(comb):
        d = 0
        for fr, to in zip(perm, perm[1:]):
            d += dists[fr][to]
        mn = 1 << 60
        for a in A:
            mn = min(mn, dists[perm[-1]][a])
        ans = min(ans, d + mn)
print(ans)
0