結果

問題 No.3158 Collect Stamps
コンテスト
ユーザー kmmtkm
提出日時 2025-05-18 13:32:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 375 ms / 2,000 ms
コード長 1,027 bytes
コンパイル時間 581 ms
コンパイル使用メモリ 82,208 KB
実行使用メモリ 90,152 KB
最終ジャッジ日時 2025-05-18 13:32:36
合計ジャッジ時間 7,312 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

INF = 10 ** 18
ans = INF

# bit DP
# dp[visited][last] = 最後に訪れた場所がlast で、訪れた場所の集合がvisited であるときの、時間の最小値

dp = [[INF] * N for _ in range(1 << N)]
# 1か所だけ訪れるパターンは0
for i in range(N):
	dp[1 << i][i] = 0


for visited in range(1 << N):
	for next_last in range(N):
		if visited & (1 << next_last):
			# 既にnext_last を訪れていたら何もしない
			continue
		new_visited = visited + (1 << next_last)
		for last in range(N):
			# 既に訪れている場所の中で、最後に訪れた場所を全探索
			if visited & (1 << last):
				dp[new_visited][next_last] = min(dp[new_visited][next_last],
												dp[visited][last] + T[last][next_last])

for visited in range(1 << N):
	if visited.bit_count() < M:
		continue
	for last in A:
		ans = min(ans, dp[visited][last])

print(ans)
0