Problem:


Score : 500 points

Problem Statement

We have N locked treasure boxes, numbered 1 to N.

A shop sells M keys. The i-th key is sold for a_i yen (the currency of Japan), and it can unlock b_i of the boxes: Box c_{i1}, c_{i2}, ..., c_{i{b_i}}. Each key purchased can be used any number of times.

Find the minimum cost required to unlock all the treasure boxes. If it is impossible to unlock all of them, print -1.

Constraints

All values in input are integers.

1 \leq N \leq 12

1 \leq M \leq 10^3

1 \leq a_i \leq 10^5

1 \leq b_i \leq N

1 \leq c_{i1} < c_{i2} < ... < c_{i{b_i}} \leq N

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
c_{11} c_{12} ... c_{1{b_1}}
:
a_M b_M
c_{M1} c_{M2} ... c_{M{b_M}}

Output

Print the minimum cost required to unlock all the treasure boxes.
If it is impossible to unlock all of them, print -1.

Sample Input 1

2 3
10 1
1
15 1
2
30 2
1 2

Sample Output 1

25

We can unlock all the boxes by purchasing the first and second keys, at the cost of 25 yen, which is the minimum cost required.

Sample Input 2

12 1
100000 1
2

Sample Output 2

-1

We cannot unlock all the boxes.

Sample Input 3

4 6
67786 3
1 3 4
3497 1
2
44908 3
2 3 4
2156 3
2 3 4
26230 1
2
86918 1
3

Sample Output 3

69942



Sample input:
2 3
10 1
1
15 1
2
30 2
1 2


Sample output:
25

Submission status: Accepted

Solution code:
from functools import reduce
INF = 10 ** 7
N, M = map(int, input().split())
L = 1 << N
table = [INF] * L
table[0] = 0
for m in range(M):
    cost, _ = map(int, input().split())
    match = reduce(lambda a, b: a | b, (1 << shamt for shamt in map(lambda n: int(n) - 1, input().split())))
    for l in range(L):
        now = table[l]
        if l and not now:
            continue
        table[l | match] = min(now + cost, table[l | match])
print(table[L - 1] if table[L - 1] != INF else -1)

Submission status: Accepted

Solution code:
from functools import reduce
INF = 10 ** 7
N, M = map(int, input().split())
L = 1 << N
keys = [0] * M
for m in range(M):
    cost, _ = map(int, input().split())
    match = reduce(lambda a, b: a | b, (1 << shamt for shamt in map(lambda n: int(n) - 1, input().split())))
    keys[m] = cost, match
table = [[INF] * L for _ in range(M + 1)]
table[0][0] = 0
for m in range(M):
    cost, match = keys[m]
    for l in range(L):
        now = table[m][l]
        if l and not now:
            continue
        table[m + 1][l] = min(now, table[m + 1][l])
        table[m + 1][l | match] = min(now + cost, table[m + 1][l | match])
print(table[M][L - 1] if table[M][L - 1] != INF else -1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N,M = map(int,readline().split())
k = 2**N
dp = [INF for i in range(k)]
dp[0] = 0

for i in range(M):
    a,b = map(int,readline().split())
    c = list(map(int,readline().split()))
    d = sum(1<<(ci-1) for ci in c)
    dpnew = dp[:]
    for j in range(k):
        dpnew[j|d] = min(dp[j]+a,dpnew[j|d])
    dp = dpnew

print(dp[2**N-1] if dp[2**N-1] != INF else -1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N,M = map(int,readline().split())
k = 2**N
dp = [INF]*k 
dp[0] = 0

for i in range(M):
    a,b = map(int,readline().split())
    c = list(map(int,readline().split()))
    d = sum(1<<(ci-1) for ci in c)
    dpnew = dp[:]
    for j in range(k):
        dpnew[j|d] = min(dp[j]+a,dpnew[j|d])
    dp = dpnew

print(dp[2**N-1] if dp[2**N-1] != INF else -1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N,M = map(int,readline().split())
k = 2**N
dp = [[INF]*k for i in range(M+1)]
dp[0][0] = 0

for i in range(M):
    a,b = map(int,readline().split())
    c = list(map(int,readline().split()))
    d = sum(1<<(ci-1) for ci in c)
    for j in range(k):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j])
        dp[i+1][j|d] = min(dp[i][j|d],dp[i][j]+a,dp[i+1][j|d])

print(dp[M][2**N-1] if dp[M][2**N-1] != INF else -1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N,M = map(int,readline().split())
k = 2**N
dp = [[INF]*k for i in range(M+1)]
dp[0][0] = 0

for i in range(M):
    a,b = map(int,readline().split())
    c = list(map(int,readline().split()))
    d = sum(2**(ci-1) for ci in c)
    for j in range(k):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j])
        dp[i+1][j|d] = min(dp[i][j|d],dp[i][j]+a,dp[i+1][j|d])

print(dp[M][2**N-1] if dp[M][2**N-1] != INF else -1)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

N,M = map(int,readline().split())
dp = [[INF]*(2**N) for i in range(M+1)]
dp[0][0] = 0

for i in range(M):
    a,b = map(int,readline().split())
    c = list(map(int,readline().split()))
    d = sum(2**(ci-1) for ci in c)
    for j in range(2**N):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j])
        dp[i+1][j|d] = min(dp[i][j|d],dp[i][j]+a,dp[i+1][j|d])

print(dp[M][2**N-1] if dp[M][2**N-1] != INF else -1)

Submission status: Accepted

Solution code:
# N = int(input())
N, M = [int(i) for i in input().split()]
key = []
for i in range(M):
    a, b = [int(_) for _ in input().split()]
    cs = [int(_) for _ in input().split()]
    s = 0
    for c in cs:
        c -= 1
        s |= 1 << c
    key.append([s, a])

INF = 10**9
dp = [INF for i in range(2**N)]
dp[0] = 0
for i in range(2**N):
    for j in range(M):
        t = i | key[j][0]
        cost = key[j][1]
        dp[t] = min(dp[t], dp[i] + cost)
ans = dp[-1]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
INF = 10 ** 10
n, m = map(int, input().split())
dp = [[INF] * (2 ** n) for _ in range(m + 1)]
a = [0] * m
c = [0] * m
for i in range(m):
    a[i], b = map(int, input().split())
    t = 0
    for k in list(map(int, input().split())):
        t += 1 << (k - 1)
    c[i] = t
dp[0][0] = 0
for i in range(m):
    for j in range(2 ** n):
        dp[i + 1][j | c[i]] = min(dp[i + 1][j | c[i]], dp[i][j] + a[i])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
ans = dp[m][(1 << n) - 1]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split()) 
asl = []
for _ in range(M):
    a, b = map(int, input().split()) 
    cl = list(map(int, input().split())) 
    s = 0
    for c in cl:
        s += 1<<(c-1)
    asl.append([a,s])

INF = 10**8
dp = [INF]*(2**N)
dp[0] = 0
for i in range(2**N):
    for as_v in asl:
        a, s = as_v
        dp[i|s] = min(dp[i]+a ,dp[i|s])

ans = dp[2**N-1]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N,M = (int(x) for x in input().split())
abc = [[None] * 3 for _ in range(M)]
check = set()
for x in abc:
    x[0],x[1] = (int(x) for x in input().split())
    x[2] = list(map(int, input().split()))
    check = check | set(x[2])
if len(check) < N:
    print('-1')
else:
    a = [x[0] for x in abc]
    c = [0] * (M+1)
    dp = [[float('inf')] * pow(2,N) for _ in range(M+1)]
    for i in range(1,M+1):
        c[i] = sum(pow(2,y-1) for y in abc[i-1][2])
    for i in range(M+1):
        dp[i][0] = 0
    for i in range(1,M+1):
        for j in range(pow(2,N)):
            dp[i][j] = min(dp[i][j],dp[i-1][j])
            dp[i][j|c[i]] = min(dp[i][j|c[i]],dp[i][j]+a[i-1])
    print(dp[M][pow(2,N)-1])

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    dp = [10**10 for _ in [0]*(2**n)]
    dp[0] = 0
    for _ in range(m):
        a,b = map(int,ipt().split())
        c = [int(i) for i in ipt().split()]
        opn = 0
        for i in c:
            opn += 2**(i-1)
        for i in range(2**n):
            if i&opn == 0:
                continue
            elif dp[i] > dp[i-(i&opn)]+a:
                dp[i] = dp[i-(i&opn)]+a

    if dp[2**n-1] >= 10**10:
        print(-1)
    else:
        print(dp[2**n-1])
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
dp=[10**10]*(1<<N)
dp[0]=0
for i in range(M):
  a,b=map(int,input().split()) 
  c=list(map(int, input().split()))
  d=0
  for j in c:
    d|=1<<j-1
  for k in range(1<<N):
    dp[k|d]=min(dp[k|d],dp[k]+a)
if dp[-1]==10**10:
  print(-1)
else:
  print(dp[-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())

dp = [float('inf')] * (1 << n)
dp[0] = 0
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))

    SS = sum([1 << (cc - 1) for cc in c])
    for S in range(1 << n):
        dp[S | SS] = min(dp[S | SS], dp[S] + a)

if dp[-1] == float('inf'):
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    N,M = map(int,input().split())

    key = []
    for i in range(M):
        a,_ = map(int,input().split())

        bit = 0
        for c in set(map(int,input().split())):
            bit += 1<<(c-1)

        key.append((a,bit)) # 値段, 開ける宝箱のbit

    dp = [[INF] * (2**N) for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        for j in range(2**N):
            cost,bit = key[i]

            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
            dp[i+1][j|bit] = min(dp[i+1][j|bit],dp[i][j] + cost)

    last = dp[-2][-1]
    print(last if 0 < last < INF else -1)



if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,m=map(int,input().split())
    dp=[10**10]*(1<<n)
    dp[0]=0
    for i in range(m):
        a,b=map(int,input().split())
        C=list(map(int,input().split()))
        d=0
        for c in C:
            d|=1<<(c-1)
        for j in range(1<<n):
            dp[j|d]=min(dp[j|d],dp[j]+a)
    if dp[-1]==10**10:
        print(-1)
    else:
        print(dp[-1])
        
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()

N,M = map(int,S().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(i) for i in S().split()))
    C.append(sum(1<<(int(i)-1) for i in S().split()))

dp = [10**8+1]*(1<<N)
dp[0] = 0

for i in range(1<<N):
    for j in range(M):
        a,b = AB[j]
        c = C[j]
        m = i|c
        dp[m] = min(dp[m],dp[i]+a)

if dp[-1] == 10**8+1:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()

N,M = map(int,S().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(i) for i in S().split()))
    C.append(sum(1<<(int(i)-1) for i in S().split()))

dp = [10**8+1]*(1<<N)
dp[0] = 0

for i in range(1<<N):
    for (a,b),c in zip(AB,C):
        m = i|c
        dp[m] = min(dp[m],dp[i]+a)

if dp[-1] == 10**8+1:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()

N,M = map(int,S().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(i) for i in S().split()))
    C.append(sum(1<<(int(i)-1) for i in S().split()))

dp = [10**8+1]*(1<<N)
dp[0] = 0

for i in range(1<<N):
    for (a,b),c in zip(AB,C):
        dp[i|c] = min(dp[i|c],dp[i]+a)

if dp[-1] == 10**8+1:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()

N,M = map(int,S().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(i) for i in S().split()))
    C.append(sum(1<<(int(i)-1) for i in S().split()))

dp = [10**8+1]*(1<<N)
dp[0] = 0

for i in range(1<<N):
    for j in range(M):
        a,b = AB[j]
        c = C[j]
        dp[i|c] = min(dp[i|c],dp[i]+a)

if dp[-1] == 10**8+1:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()

N,M = map(int,S().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(i) for i in S().split()))
    C.append(sum(1<<(int(i)-1) for i in S().split()))

dp = [10**18]*(1<<N)
dp[0] = 0

for i in range(1<<N):
    for j in range(M):
        a,b = AB[j]
        c = C[j]
        dp[i|c] = min(dp[i|c],dp[i]+a)

if dp[-1] == 10**18:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()

N,M = map(int,S().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(i) for i in S().split()))
    C.append(sum(1<<(int(i)-1) for i in S().split()))

dp = [float('inf')]*(1<<N)
dp[0] = 0

for i in range(1<<N):
    for j in range(M):
        a,b = AB[j]
        c = C[j]
        dp[i|c] = min(dp[i|c],dp[i]+a)

if dp[-1] == float('inf'):
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
key = [[] for _ in range(M)]
for i in range(M):
    a, _ = map(int, input().split())
    # 空けることができる宝箱をbitで表す
    c = 0
    for v in list(map(int, input().split())):
        c += pow(2, v-1)
    key[i] = [a, c]

status_count = pow(2, N)
INF = 10 ** 30
# keyの各要素の先頭が値段になってる
dp = [INF] * (status_count)
dp[0] = 0
for a, c in key:
    # 今対象の鍵を購入したときの最小値を求める
    for i in range(status_count):
        dp[i | c] = min(dp[i | c], dp[i] + a)

print(dp[-1] if dp[-1] < INF else -1)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit


def main():
    INF = float('inf')
    input = stdin.buffer.readline
    n, m = map(int, input().split())
    dp = [[INF] * (1 << n) for _ in range(m)]

    for i in range(m):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))

        dp[i][0] = 0

        tmp = 0
        for ci in c:
            tmp |= 1 << (ci - 1)

        if i == 0:
            dp[i][tmp] = a
        else:
            for j in range(1 << n):
                dp[i][j] = min(dp[i][j], dp[i - 1][j])
                dp[i][j | tmp] = min(dp[i][j | tmp], dp[i - 1][j] + a)

    ans = dp[m - 1][-1]
    if ans == INF:
        print(-1)
    else:
        print(dp[m - 1][-1])


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:


def compute(subset):
	r = 0
	for i in range(len(subset)):
		r +=  (1 << (subset[i]-1))
	return r	

n,m = map(int, raw_input().split(' '))
keys= []
for _ in range(m):
	cost, nk = map(int, raw_input().split(' '))
	keys.append((cost, compute( map(int, raw_input().split(' ')) )))

h = {0:0}
for cost,mask in keys:
	for uu in range(2 ** n - 1,-1,-1):
		cm = uu & mask
		cm = uu ^ (cm) 
		h[uu] = min(h[uu] if uu in h else +float('inf'), (h[cm] if cm in h else +float('inf')) + cost )
print h[2 ** n -1] if (2 ** n -1) in h and h[(2 ** n) -1] < float('inf') else -1

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Cost = []
for i in range(M):
    a, b = map(int, input().split())
    c = 0
    K = list(map(int, input().split()))
    for j in range(b):
        c += 2**(K[j]-1)
    Cost.append([c, a])

dp = [[float("inf")]*(2**N+1) for _ in range(M+1)]
for i in range(M+1):
    dp[i][0] = 0

for i in range(1, M+1):
    for j in range(2**N):
        k = Cost[i-1][0] | j
        dp[i][j] = min(dp[i-1][j], dp[i][j])
        dp[i][k] = min([dp[i-1][j] + Cost[i-1][1], dp[i-1][k], dp[i][k]])

if dp[M][2**N-1] == float("inf"):
    print(-1)
else:
    print(dp[M][2**N-1])

Submission status: Accepted

Solution code:
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N,M = map(int,(input().split()))
dp = [float("inf")]*(2**N)
dp[0] = 0
for i in range(M):
    a,b = map(int,(input().split()))
    c = list(map(int,(input().split())))
    d = 0
    for j in c:
        d += 2**(j-1)
    for j in range(2**N):
        dp[j|d] = min(dp[j|d],dp[j]+a)

ans = dp[-1]
if ans != float("inf"):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
def main():
  n, m = map(int, input().split())
  
  dp = [0]*(2**n)
  len_dp = len(dp)

  key_list = dict()
  sub = 1
  for i in range(n):
    key_list[i+1] = sub
    sub *= 2

  for _ in range(m):
    a, b = map(int, input().split())
    c = [int(x) for x in input().split()]
    key = 0
    for value in c:
      key += key_list[value]
    for i in range(len_dp-1, -1, -1):
      if i == 0 or dp[i]:
        if dp[i|key]:
          dp[i|key] = min([dp[i]+a, dp[i|key]])
        else:
          dp[i|key] = dp[i]+a

  print(dp[len_dp-1] if dp[len_dp-1] else -1)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
INF = 10**10

B = [INF]*(1<<n)
B[0] = 0

for _ in range(m):
  a,b = map(int,input().split())
  C = list(map(int,input().split()))
  opens = 0
  for c in C:
    opens |= (1<<(c-1))
  
  for i in range(2**n):
    if B[i|opens] > B[i]+a:
      B[i|opens] = B[i]+a

if B[(1<<n)-1]==INF:
  print(-1)
else:
  print(B[(1<<n)-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,M=map(int,input().split())
lst=[0]*M
for i in range(M):
 a,b=map(int,input().split())
 c=set(map(int,input().split()))
 d=0
 for n in c:
  d+=2**(n-1)
  lst[i]=(a,d)
ans=[[float("inf") for e in range(2**N)] for f in range(M+1)]
ans[0][0]=0
for j in range(M):
 for i in range(2**N):
  e= i-(lst[j][1]&i)
  ans[j+1][i]=min(ans[j][e]+lst[j][0],ans[j][i])
if ans[M][2**N-1]==float("inf"):
 print(-1)
else:
 print(ans[M][2**N-1])

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
lst=[0]*M
for i in range(M):
 a,b=map(int,input().split())
 c=list(map(int,input().split()))
 d=0
 for n in range(b):
  d+=2**(c[n]-1)
  lst[i]=(a,d)
ans=[[float("inf") for e in range(2**N)] for f in range(M+1)]
ans[0][0]=0
for j in range(M):
 for i in range(2**N):
  e= i-(lst[j][1]&i)
  ans[j+1][i]=min(ans[j][e]+lst[j][0],ans[j][i])
if ans[M][2**N-1]==float("inf"):
 print(-1)
else:
 print(ans[M][2**N-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
BIT = 2 ** N
dp =[[float("inf") for _ in range(BIT)] for _ in range(M + 1)]
dp[0][0] = 0

for i in range(M):
    A, B = map(int, input().split())
    C = list(map(int, input().split()))
    x = sum([2 ** (c - 1) for c in C])
    for j in range(BIT):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][x|j] = min(dp[i][j] + A, dp[i + 1][x|j])

ans = dp[M][BIT - 1]
if ans != float("inf"):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())

dp =[[float("inf") for _ in range(2 ** N)] for _ in range(M + 1)]
dp[0][0] = 0

for i in range(M):
    A, B = map(int, input().split())
    C = list(map(int, input().split()))
    x = sum([2 ** (c - 1) for c in C])
    for j in range(2 ** N):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][x|j] = min(dp[i][j] + A, dp[i + 1][x|j])

ans = dp[M][2 ** N - 1]
if ans != float("inf"):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())

dp =[[float("inf") for _ in range(2 ** N)] for _ in range(M + 1)]
dp[0][0] = 0

for i in range(M):
    A, B = map(int, input().split())
    C = list(map(int, input().split()))
    tmp = [0 for _ in range(N)]
    for c in C:
        tmp[c - 1] = 1
    x = int("".join(map(str, tmp)), 2)
    for j in range(2 ** N):
        dp[i + 1][x|j] = min(dp[i][x|j], dp[i][j] + A, dp[i + 1][x|j])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])

ans = dp[M][2 ** N - 1]
if ans != float("inf"):
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:

n, m = map(int, input().split())
ab = []
c= []
keys = ["" for _ in range(m)]

for i in range(m):
    ab.append(list(map(int, input().split())))
    kari = list(map(int, input().split()))
    c.append(kari)
    for j in range(n):
        if j+1 in kari:
            keys[i] = keys[i]+"1"
        else:
            keys[i] = keys[i] + "0"

all_patterns = ["0","1"]
options = ["0", "1"]

for _ in range(n-1):
    all_patterns = [j+i for i in (options) for j in all_patterns]

dp = [1e+10 for i in range(2**n)]
dp[0] = 0

#%%
for j in range(m):
    for i in range(len(dp)):
        kari1 = dp[i]+ab[j][0]
        kari2 = dp[i|int(keys[j],2)]
        if kari1 < kari2:
            dp[i|int(keys[j],2)] = kari1

if dp[-1] != 1e+10:
    print(dp[-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
lis = []
for i in range(m):
    tmp = list(map(int,input().split()))
    tmp.extend(list(map(int,input().split())))
    lis.append(tmp)

dp = [[1000000000 for i in range(2**n)]for i in range(m+1)]
dp[0][0]=0
for i in range(m):
    clis = 0
    for j in lis[i][2:]:
        clis += 2**(j-1)

    for sin in range(2**n):
        #print(dp[i][sin]+lis[i][0],clis|sin)
        dp[i+1][clis|sin] = min(dp[i][sin]+lis[i][0],dp[i+1][clis|sin])
    for sin in range(2**n):
        dp[i+1][sin] = min(dp[i+1][sin],dp[i][sin])

#print(lis)
#print(*dp,sep="\n")
if dp[m][-1]==1000000000:
    print(-1)
else:
    print(dp[m][-1])

Submission status: Accepted

Solution code:
n ,m= list(map(int,input().split()))
kagi = [[]for _ in range(m)] 
#a円　b種類開けられる
for i in range(m):
    a,b =  list(map(int,input().split()))
    X =  list(map(int,input().split()))
    bit = 0
    for x in X:
        bit |= 2**(x-1)
    kagi[i] = [a,bit]

ok = 2**n-1#全部空いたらこれ
kagi.sort(key=lambda x: x[1])
zenkai = 2**n
dp = [float('inf')]*int(zenkai+1)
dp[0] = 0
for i in range(2**n):
    if dp[i] == float('inf'):
        continue
    for j in range(m):
        s = i|kagi[j][1]
        # print(s)
        dp[s] = min(dp[s],dp[i] + kagi[j][0])
# print(dp)
if dp[zenkai-1] == float('inf'):
    print(-1)
else:
    print(dp[zenkai-1])

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N, M = rl()
A = []
Cs = []
for i in range(M):
	a, b = rl()
	C = rl()
	A.append(a)
	Cs.append(C)

def get_bit(C):
	b = 0
	for c in C:
		b = b | (1 << (c-1))
	return b
bits =[]
for C in Cs:
	b = get_bit(C)
	bits.append(b)

start = 0
end = 2**N-1

import heapq

heap = []
heapq.heappush(heap, (0, start))

visited = {}
ans = -1
while heap:
	c, n = heapq.heappop(heap)
	if n == end:
		ans = c
		break
	for i, b in enumerate(bits):
		m = n | b
		nc = c + A[i]
		if m in visited and nc >= visited[m]:
			continue
		visited[m] = nc
		heapq.heappush(heap, (nc, m))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def solve():
    INF = 10**10

    N, M = map(int, input().split())
    keys = []
    costs = []
    for _ in range(M):
        a, b = map(int, input().split())
        costs.append(a)
        cs = list(map(int, input().split()))
        key = 0
        for c in cs:
            key |= 1<<(c-1)
        keys.append(key)

    dp = [INF] * (1<<N)
    dp[0] = 0
    for key, cost in zip(keys, costs):
        for S in reversed(range(1<<N)):
            S2 = S | key
            c2 = dp[S] + cost
            if c2 < dp[S2]:
                dp[S2] = c2

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


solve()

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N, M = rl()
A = []
Cs = []
for i in range(M):
	a, b = rl()
	C = rl()
	A.append(a)
	Cs.append(C)

def get_bit(C):
	b = 0
	for c in C:
		b = b | (1 << (c-1))
	return b
bits =[]
for C in Cs:
	b = get_bit(C)
	bits.append(b)

start = 0
end = 2**N-1

import heapq

heap = []
heapq.heappush(heap, (0, start))

visited = {}
ans = -1
while heap:
	c, n = heapq.heappop(heap)
	if n in visited:
		continue
	if n == end:
		ans = c
		break
	visited[n] = 1
	for i, b in enumerate(bits):
		m = n | b
		if m in visited:
			continue
		cost = A[i]
		heapq.heappush(heap, (c + cost, m))
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def solve():
    INF = 10**10

    N, M = map(int, input().split())
    keys = []
    costs = []
    for _ in range(M):
        a, b = map(int, input().split())
        costs.append(a)
        cs = list(map(int, input().split()))
        key = 0
        for c in cs:
            key |= 1<<(c-1)
        keys.append(key)

    dp = [INF] * (1<<N)
    dp[0] = 0
    for S in range(1<<N):
        for key, cost in zip(keys, costs):
            S2 = S | key
            c2 = dp[S] + cost
            if c2 < dp[S2]:
                dp[S2] = c2

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


solve()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, readline().split()))

    a = [0] * m
    c = [0] * m

    for i in range(m):
        a[i], _ = list(map(int, readline().split()))
        t = list(map(int, readline().split()))
        for x in t:
            c[i] += (1 << (x - 1))

    dp = [[INF] * (1 << n) for _ in range(m)]
    dp[0][c[0]] = a[0]

    for i in range(m):
        dp[i][0] = 0

    for i in range(1, m):
        key = c[i]
        price = a[i]
        for j in range(1 << n):
            dp[i][j] = min(dp[i][j], dp[i - 1][j])
            if dp[i - 1][j] != INF:
                dp[i][j | key] = min(dp[i][j | key], dp[i - 1][j] + price)

    ans = dp[-1][-1]
    if ans == INF:
        ans = -1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ac = []
for _ in range(m):
    ai, bi = map(int, input().split())
    ci = list(map(lambda x: 2 ** (int(x) - 1) , input().split()))
    ac.append((ai, sum(ci)))

INF = 100 ** 18
dp = [INF] * (2**n)
dp[0] = 0
for ai, ci in ac:
    for j in range(0, 2**n):
        dp[j | ci] = min(dp[j | ci], dp[j] + ai)

ans = dp[2**n-1]
if ans == INF:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
c = []
a = []
for _ in range(m):
    ai, bi = map(int, input().split())
    ci = list(map(lambda x: 2 ** (int(x) - 1) , input().split()))
    a.append(ai)
    c.append(sum(ci))

INF = 100 ** 18
dp = [INF] * (2**n)
dp[0] = 0
for i in range(m):
    for j in range(0, 2**n):
        dp[j | c[i]] = min(dp[j | c[i]], dp[j] + a[i])

ans = dp[2**n-1]
if ans == INF:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
dp=[float("inf")]*(1<<n)
b=[True]*(1<<n)
p=[]
k=0
for i in range(m):
    k=0
    a,_=map(int,input().split())
    c=list(map(int,input().split()))
    for cc in c:
        k+=1<<(cc-1)
    if b[k]:
        b[k]=False
    dp[k]=min(dp[k],a)
    p.append(k)
while True:
    d=[]
    for i in p:
        for j in p:
            if dp[i|j]>dp[i]+dp[j]:
                dp[i|j]=dp[i]+dp[j]
                if b[i|j]:
                    b[i|j]=False
                    d.append(i|j)
    if len(d)==0:
        break
    for oo in d:
        p.append(oo)
if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**8
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    N,M = LI()
    key = [0]
    box = [0]
    for _ in range(M):
        k,_ = LI()
        key.append(k)
        b = 0
        for c in LI():
            b += 2**(c-1)
        box.append(b)

    dp = [[INF] * (2**N) for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(1,M+1):
        for j in range(2**N):
            dp[i][j] = min(dp[i-1][j],dp[i-1][j - (j&box[i])]+key[i])
    if dp[-1][-1] == INF:
        print(-1)
    else:
        print(dp[-1][-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
c = set()
v = {}
for i in range(m):
  a,b = map(int,readline().split())
  d = list(map(int,readline().split()))
  e = 0
  for j in d:
    e += 2**(j-1)
  if i >= 1:
    s = list(c)
    for k in s:
      if not k|e in c:
        c.add(k|e)
        v[k|e] = a+v[k]
      else:
        v[k|e] = min(v[k|e],a+v[k])
  if not e in c:
    c.add(e)
    v[e] = a
  else:
    v[e] = min(v[e],a)
    
if 2**n-1 in c:
  print(v[2**n-1])
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
c = set()
v = {}
for i in range(m):
  a,b = map(int,readline().split())
  d = list(map(int,readline().split()))
  e = 0
  for j in d:
    e += 2**(j-1)
  if i >= 1:
    s = list(c)
    for k in s:
      if not k|e in c:
        c.add(k|e)
        v[k|e] = a+v[k]
      else:
        v[k|e] = min(v[k|e],a+v[k])
  if not e in c:
    c.add(e)
    v[e] = a
  else:
    v[e] = min(v[e],a)
    
if 2**n-1 in c:
  print(v[2**n-1])
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


MOD = 10 ** 9 + 7
sys.setrecursionlimit(20000000)
INF = float("inf")


def main():
    N, M = map(int, input().split())
    key = []
    for _ in range(M):
        a, b = map(int, input().split())
        C = list(map(lambda x: int(x) - 1, input().split()))
        state = 0
        for c in C:
            state += 2 ** c
        key.append((a, state))
    dp = [INF for _ in range(2 ** N)]
    dp[0] = 0
    for i in range(2 ** N - 1):
        for k in range(M):
            state = key[k][1]
            tmp = dp[i] + key[k][0]
            if dp[i | state] > tmp:
                dp[i | state] = tmp
    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())

    dp = [INF for i in range(1 << N)]
    dp[0] = 0

    key = []
    for _ in range(M):
        a, b = map(int, input().split())
        C = tuple(map(lambda x: int(x) - 1, input().split()))
        status = 0
        for c in C:
            status += 2 ** c
        key.append((a, status))

    for a, status in key:
        if dp[status] > a:
            dp[status] = a

    for i in range(2 ** N - 1):
        for a, status in key:
            new_status = status | i
            if dp[new_status] > dp[i] + a:
                dp[new_status] = dp[i] + a

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


if __name__ == "__main__":
    main()