結果
問題 |
No.3158 Collect Stamps
|
ユーザー |
![]() |
提出日時 | 2025-05-23 20:01:40 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,261 bytes |
コンパイル時間 | 506 ms |
コンパイル使用メモリ | 82,044 KB |
実行使用メモリ | 86,096 KB |
最終ジャッジ日時 | 2025-05-23 20:01:45 |
合計ジャッジ時間 | 4,542 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 1 WA * 2 TLE * 1 -- * 31 |
ソースコード
import sys, time, random, heapq, math, itertools from collections import deque, Counter, defaultdict #from sortedcontainers import SortedSet, SortedList from bisect import bisect, bisect_left, bisect_right import heapq as hq from functools import cache, cmp_to_key def debug(*x):print('debug:',*x, file=sys.stderr) sys.setrecursionlimit(300000) input = lambda: sys.stdin.readline().rstrip() ii = lambda: int(input()) mi = lambda: map(int, input().split()) li = lambda: list(mi()) inf = 2 ** 61 - 1 mod = 998244353 N,M,K = mi() A = li() A = set(A) T = [li() for _ in range(N)] for k in range(N): for i in range(N): for j in range(N): T[i][j] = min(T[i][j], T[i][k] + T[k][j]) ans = inf for bit in range(1<<N): if bit.bit_count() <= M: continue l = [i for i in range(N) if (bit >> i) & 1] if len(l) < M: continue for comb in itertools.combinations(l, M): for p in itertools.permutations(comb): cnt = 0 for i in range(M - 1): cnt += T[p[i]][p[i+1]] last = p[-1] if last in A: ans = min(ans, cnt) else: for a in A: ans = min(ans, cnt + T[last][a-1]) print(ans)