結果

問題 No.3158 Collect Stamps
コンテスト
ユーザー kmmtkm
提出日時 2025-05-11 11:18:02
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 635 ms / 2,000 ms
コード長 1,297 bytes
コンパイル時間 377 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2025-05-11 22:05:10
合計ジャッジ時間 5,468 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

from itertools import permutations


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

# validation
assert 1 <= N <= 16
assert 1 <= M <= min(6, N)
assert A == sorted(A)
assert all(1 <= ai <= N for ai in A)
assert len(A) == K
assert all(T[i][i] == 0 for i in range(N))
assert all(1 <= T[i][j] <= 100000 or i == j
           for i in range(N) for j in range(N))

for k in range(N):
    for i in range(N):
        for j in range(N):
            assert T[i][j] <= T[i][k] + T[k][j]


A = set(ai - 1 for ai in A)


def solve():
    if M == 1:
        return 0

    ans = 10 ** 18

    for p in permutations(range(N), M):
        if p[-1] not in A:
            continue

        ans = min(ans, sum(T[p[i]][p[i+1]] for i in range(M-1)))

    return ans


def solve2():
    ans = 10 ** 18

    patterns = []
    for i in range(1 << N):
        if i.bit_count() == M:
            patterns.append(i)

    for i in patterns:
        poses = []
        for j in range(N):
            if i & (1 << j):
                poses.append(j)

        for p in permutations(poses):
            if p[-1] not in A:
                continue
            ans = min(ans, sum(T[p[i]][p[i+1]] for i in range(M-1)))

    return ans


print(solve())
0