Submission #53267478

---

Source Code Expand

N, M = map(int, input().split())
key = []
for _ in range(M):
    a, b = map(int, input().split())
    s = 0 # i 番目の鍵で開けることのできる宝箱の集合
    c = list(map(lambda x: int(x) - 1, input().split()))
    for i in c:
        s |= (1 << i)
    key.append((a, s))

INF = 10**18
# dp[S] := 集合 S の宝箱を開けるのに必要な費用の最小値
dp = [INF]*(1 << N)
dp[0] = 0
for S in range(1 << N):
    for k, v in key:
        dp[S | v] = min(dp[S | v], dp[S] + k)

if dp[(1 << N) - 1] != INF:
    print(dp[(1 << N) - 1])
else:
    print(-1)

Submission Info

Judge Result