結果
問題 | No.3158 Collect Stamps |
ユーザー |
|
提出日時 | 2025-05-11 11:09:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 178 ms / 2,000 ms |
コード長 | 1,297 bytes |
コンパイル時間 | 386 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 76,792 KB |
最終ジャッジ日時 | 2025-05-11 22:04:30 |
合計ジャッジ時間 | 4,307 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 |
ソースコード
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())