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: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a = [0]*M
b = [0]*M
c = [0]*M
for i in range(M):
    a[i], b[i] = map(int, input().split())
    cc = list(map(int, input().split()))
    for ccc in cc:
        ccc -= 1
        c[i] += (1 << ccc)

INF = float('inf')
dp = [[INF]*5000 for _ in range(M+1)]
dp[0][0] = 0

for i in range(M):
    for j in range((1 << N)):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        nj = j | c[i]
        dp[i+1][nj] = min(dp[i+1][nj], dp[i][j] + a[i])
if dp[M][(1 << N)-1] == INF:
    print(-1)
else:
    print(dp[M][(1 << N)-1])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
p = []
for k in range(m):  
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    key = 0
    for i in c:
        key += 2**(i-1)
    p.append([a,key])
inf = 10**9
dp = []
for u in range(m+1):
    dp.append([inf for i in range(2**n)])
dp[0][0] = 0
for i in range(m):
    for k in range(2**n):
        dp[i+1][k] = dp[i][k]
    for k in range(2**n):
        dp[i+1][k|p[i][1]] = min(dp[i][k|p[i][1]],dp[i][k]+p[i][0],dp[i+1][k|p[i][1]])
if dp[-1][-1] >= inf:
    print(-1)
else:
    print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
input = sys.stdin.buffer.readline
INF = float("inf")

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

    # dp[i][j] : i番目の鍵までを使い, j の組み合わせの箱を開けるのに必要な最小費用
    dp = [[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()))

        # 開錠可能な箱をbitで表現する
        bit = 0
        for x in c:
            bit |= 1 << (x-1)
        
        for j in range(2**N):
            # 鍵を使う場合
            dp[i+1][j | bit] = min(dp[i+1][j | bit], dp[i][j] + a)
            # 鍵を使わない場合
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    
    if dp[-1][-1] == INF:
        print(-1)
    else:
        print(dp[-1][-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
input = sys.stdin.buffer.readline
INF = float("inf")

def main():
    N,M = map(int,input().split())
    A,B,C = [],[],[]
    for i in range(M):
        a,b =map(int,input().split())
        c = list(map(int,input().split()))
        A.append(a)
        B.append(b)
        C.append(c)

    # dp[i][j] : i番目の鍵までを使い, j の組み合わせの箱を開けるのに必要な最小費用
    dp = [[INF for _ in range(2**N)] for _ in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        a,b,c = A[i],B[i],C[i]
        bit = 0
        # 開錠可能な箱をbitで表現する
        for x in c:
            bit |= 1 << (x-1)
        for j in range(2**N):
            # 鍵を使う場合
            dp[i+1][j | bit] = min(dp[i+1][j | bit], dp[i][j] + a)
            # 鍵を使わない場合
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    
    if dp[-1][-1] == INF:
        print(-1)
    else:
        print(dp[-1][-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[]
c=[]
for _ in range(m):
  ab.append(list(map(int,input().split())))
  c.append(list(map(int,input().split())))
dp={():0}
for i in range(m):
  a,b=ab[i]
  sc=set(c[i])
  dptmp={}
  for k,v in dp.items():
    s=set(k)
    s|=sc
    t=tuple(sorted(list(s)))
    dptmp[t]=min(v+a,dp[t] if t in dp else float('inf'),dptmp[t] if t in dptmp else float('inf'))
  dp.update(dptmp)

t=tuple(range(1,n+1))
if t in dp:
  print(dp[t])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
INF = 10 ** 18
N, M = map(int, input().split())
dp = [[INF for _ in range(1 << N)] for _ in range(M + 1)]
cost = [0] * M
bit = [0] * M
for i in range(M):
    cost[i], b = map(int, input().split())
    c = list(map(int, input().split()))
    d = 0
    for j in range(len(c)):
        d |= 1 << (c[j] - 1)
    bit[i] = d

dp[0][0] = 0
for i in range(M):
    for j in range(1 << N):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        to = bit[i] | j
        dp[i + 1][to] = min(dp[i + 1][to], dp[i][j] + cost[i])

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n, m = map(int, input().split())
  la, lb = [], []
  lc = []
  MAX = 10**9
  dp = [MAX] * (2 ** 13)
  dp[0] = 0
  
  for _ in range(m):
    a, b = map(int, input().split())
    la.append(a)
    lb.append(b)
    lc.append(sum([1 << c for c in map(int, input().split())]))
    
  for a, c in zip(la, lc):
    for ic in range(len(dp)):
      dp[c | ic] = min(a + dp[ic], dp[c | ic])
  if dp[2**(n+1)-2] != MAX:
    print(dp[2**(n+1)-2])
  else:
    print(-1)

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  n, m = map(int, input().split())
  la, lb = [], []
  lc = []
  MAX = 10**9
  dp = numpy.zeros(2 ** 13).astype(numpy.int32)
  dp[1:] = MAX
  
  for _ in range(m):
    a, b = map(int, input().split())
    la.append(a)
    lb.append(b)
    lc.append(sum([1 << c for c in map(int, input().split())]))
    
  for a, c in zip(la, lc):
    for ic in range(dp.shape[0]):
      dp[c | ic] = min(a + dp[ic], dp[c | ic])
  if (ans:=dp[2**(n+1)-2]) != MAX:
    print(ans)
  else:
    print(-1)

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

keys=[[] for _ in range(N)]
dp=[-1]*(2**N)
dp[0]=0

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

    op=2**N-1

    for cc in c:
        op-=2**(cc-1)

    for cc in c:
        keys[cc-1].append((op,a))


def rec(current):
    if dp[current]>-1:
        return dp[current]

    ret=10**10

    i=0
    tmp=current
    while tmp&1==0:
        i+=1
        tmp=tmp>>1
    
    for op,a in keys[i]:
        minc=rec(current&op)
        if minc==-1:
            continue
        ret=min(ret,a+minc)
    
    if ret==10**10:
        dp[current]=-1
        return -1
    
    dp[current]=ret
    return ret

print(rec(2**N-1))

Submission status: Time Limit Exceeded

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

dp = [[10**10 for B in range(1 << N)] for i in range(M+1)]
dp[0][0] = 0

for i in range(M):
    a, b = map(int, input().split())
    c = [int(j) for j in input().split()]
    C = sum([1 << (x-1) for x in c])

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

if dp[M][(1 << N)-1] == 10**10:
    print(-1)
else:
    print(dp[M][(1 << N)-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
s_readline = sys.stdin.readline

INF = 10**9 + 7

N, M = map(int, readline().split())
key = [()] * M

for i in range(M):
    a, b = map(int, readline().split())
    c = map(int, readline().split())
    num = 0
    for j in c:
        num += 1 << (j - 1)
    key[i] = (num, a)


def solve():

    dp = np.full(2**N, INF, np.int64)
    dp[0] = 0

    for i in range(M):

        next_dp = dp.copy()
        num, a = key[i]

        for j in range(2**N):
            if dp[j] == INF:
                continue
            else:
                next_num = j | num
                next_dp[j] = min(next_dp[j], dp[j])
                next_dp[next_num] = min(next_dp[next_num], dp[j] + a)

        dp = next_dp

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

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
  N, M = map(int, input().split())
  inf =  10**9
  p = 1<<N
  dp = [[inf]*p for _ in range(M+1)]
  for i in range(M+1):
    dp[i][0] = 0
  for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    c_bit = sum([1<<(c-1) for c in C])
    for j in range(p):
      #print(min(dp[i][j|c_bit], dp[i][j] + a))
      dp[i+1][j|c_bit] = min(dp[i][j|c_bit], dp[i][j] + a, dp[i+1][j|c_bit])
      dp[i+1][j] = min(dp[i][j], dp[i+1][j])
  if dp[M][2**N-1] == inf:
    print(-1)
  else: 
    print(int(dp[M][2**N-1]))
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  N, M = map(int, input().split())
  inf =  10**9
  p = 2**N
  dp = [[inf]*p for _ in range(M+1)]
  for i in range(M+1):
    dp[i][0] = 0
  for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    c_bit = sum([2**(c-1) for c in C])
    for j in range(p):
      #print(min(dp[i][j|c_bit], dp[i][j] + a))
      dp[i+1][j|c_bit] = min(dp[i][j|c_bit], dp[i][j] + a, dp[i+1][j|c_bit])
      dp[i+1][j] = min(dp[i][j], dp[i+1][j])
  if dp[M][2**N-1] == inf:
    print(-1)
  else: 
    print(int(dp[M][2**N-1]))
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

def main():
  for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    c_bit = sum([2**(c-1) for c in C])
    for j in range(2**N):
      if dp[i][j] == inf:
        continue
      else:
        #print(min(dp[i][j|c_bit], dp[i][j] + a))
        dp[i+1][j|c_bit] = min(dp[i][j|c_bit], dp[i][j] + a, dp[i+1][j|c_bit])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
  if dp[M][2**N-1] == inf:
    print(-1)
  else: 
    print(int(dp[M][2**N-1]))
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

def main():
  for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    c_bit = sum([2**(c-1) for c in C])
    for j in range(2**N):
      if dp[i][j] == inf:
        continue
      else:
        #print(min(dp[i][j|c_bit], dp[i][j] + a))
        dp[i+1][j|c_bit] = min(dp[i][j|c_bit], dp[i][j] + a, dp[i+1][j|c_bit])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
  if dp[M][2**N-1] == inf:
    print(-1)
  else: 
    print(int(dp[M][2**N-1]))
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

dp = [[10**10 for _ in range(2**n)] for j in range(m)]
dp[0][0] = 0
a, b = map(int, input().split())
c = list(map(int, input().split()))
idx = 0
for cc in c:
  idx += 2**(cc-1)
for j in range(1, 2**n):
  if ~idx & j == 0:
    dp[0][j] = a

for i in range(1, m):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  idx = 0
  for cc in c:
    idx += 2**(cc-1)
  for j in range(2**n):
    dp[i][j] = min(dp[i-1][j], dp[i-1][(j|idx)^idx]+a)

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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
INF = 10 ** 7
N, M = map(int, input().split())
L = 1 << N
table = [[INF] * L for _ in range(M + 1)]
table[0][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[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: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
dp = [10 ** 8 + 1] * (1 << n)
dp[0] = 0
for _ in range(m):
  price, _ = map(int, input().split())
  treasure = sum(1 << c-1 for c in map(int, input().split()))
  for bit in range((1 << n) - 1):
    next_bit = treasure | bit
    next_cost = price + dp[bit]
    dp[next_bit] = min(dp[next_bit], next_cost)
if dp[-1] > 10 ** 8:
  print(-1)
else:
  print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
price = [0] * m
treasure = [0] * m
for i in range(m):
  price[i], _ = map(int, input().split())
  treasure[i] = sum(1 << c-1 for c in map(int, input().split()))
dp = [10 ** 8 + 1] * (1 << n)
dp[0] = 0
for bit in range((1 << n) - 1):
  cost = dp[bit]
  for i in range(m):
    next_bit = treasure[i] | bit
    next_cost = price[i] + cost
    dp[next_bit] = min(dp[next_bit], next_cost)
if dp[-1] > 10 ** 8:
  print(-1)
else:
  print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
price = [0] * m
treasure = [0] * m
for i in range(m):
  price[i], _ = map(int, input().split())
  for c in map(int, input().split()):
    treasure[i] += 1 << c-1
dp = [10 ** 8 + 1] * (1 << n)
dp[0] = 0
for bit in range((1 << n) - 1):
  cost = dp[bit]
  for i in range(m):
    next_bit = treasure[i] | bit
    next_cost = price[i] + cost
    dp[next_bit] = min(dp[next_bit], next_cost)
if dp[-1] > 10 ** 8:
  print(-1)
else:
  print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m = map(int, input().split())
price = np.zeros(m, dtype=int)
treasure = np.zeros(m, dtype=int)
for i in range(m):
  price[i], _ = map(int, input().split())
  for c in map(int, input().split()):
    treasure[i] += 1 << (c - 1)
dp = np.ones(1 << n, dtype=int) * (10 ** 8 + 1)
dp[0] = 0
for bit in range(1 << n):
  next_bit = treasure | bit
  next_cost = price + dp[bit]
  for i in range(m):
    dp[next_bit[i]] = min(dp[next_bit[i]], next_cost[i])
if dp[-1] > 10 ** 8:
  print(-1)
else:
  print(dp[-1])

Submission status: Time Limit Exceeded

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

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: Time Limit Exceeded

Solution code:
INF = float("INF")
n,m = map(int,input().split())
A = [0]*m
C = [0]*m
for i in range(m):
    a,b = map(int,input().split())
    A[i] = a
    for j in map(int,input().split()):
        j -= 1
        C[i] += 1<<j 

dp = [[INF]*(m+1) for _ in range(1<<n)]
dp[0][0] = 0
for i in range(1<<n):
    for j in range(m):
        dp[i][j+1] = min(dp[i][j],dp[C[j]&i^i][j] + A[j])

# for i in range(1<<n): print(dp[i])
print(dp[-1][-1] if dp[-1][-1] != INF else -1)

Submission status: Time Limit Exceeded

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

lll = []
for i in range(m):
  a, b = list(map(int, input().split(' ')))
  ccc = list(map(int, input().split(' ')))
  lll.append((a, b, set(ccc)))

def f(index, cost, opened):
  if index == m:
    return cost if len(opened) == n else 99999999999999999
  used = f(index + 1, cost + lll[index][0], opened.union(lll[index][2]))
  not_used = f(index + 1, cost, opened)
  return min(used, not_used)
ans = f(0, 0, set())
print(ans if ans < 99999999999999999 else -1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
inf = 10 ** 9
dp = [0] + [inf] * ((1 << n) - 1)
for _ in range(m):
    newdp = [p for p in dp]
    a, b = map(int, input().split())
    c = sum(1 << (int(i) - 1) for i in input().split())
    for bits in range(len(dp)):
        newdp[bits | c] = min(newdp[bits | c], dp[bits] + a)
    dp = newdp
print(-1 if dp[-1] == inf else dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a,c=[],[]
for _ in range(m):
  a.append(list(map(int,input().split()))[0])
  c.append(sum((1<<(int(i)-1)) for i in input().split()))
inf=float('inf')
dp=[inf]*(1<<n)
dp[0]=0
for i in range(2**n):
  for j in range(m):
    dp[i|c[j]]=min(dp[i|c[j]],dp[i]+a[j])
print(dp[-1] if inf!=dp[-1] else-1)

Submission status: Time Limit Exceeded

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_dict = dict()
for pattern in all_patterns:
    dp_dict[pattern] = 1e+10
dp_dict["0"*n] = 0

for j in range(m):
    for key in dp_dict.keys():
        kari1 = dp_dict[key]+ab[j][0]
        kari2 = dp_dict[format(int(key,2)|int(keys[j],2),"0"+str(n)+"b")]
        if kari1 < kari2:
            dp_dict[format(int(key,2)|int(keys[j],2),"0"+str(n)+"b")] = kari1

if dp_dict["1"*n] != 1e+10:
    print(dp_dict["1"*n])
else:
    print(-1)

Submission status: Time Limit Exceeded

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_dict = dict()
for pattern in all_patterns:
    dp_dict[pattern] = 1e+10
dp_dict["0"*n] = 0

for j in range(m):
    for key in dp_dict.keys():
        kari1 = dp_dict[key]+ab[j][0]
        kari2 = dp_dict[format(int(key,2)|int(keys[j],2),"0"+str(n)+"b")]
        if kari1 < kari2:
            dp_dict[format(int(key,2)|int(keys[j],2),"0"+str(n)+"b")] = kari1

if dp_dict["1"*n] != 1e+10:
    print(dp_dict["1"*n])
else:
    print(-1)

Submission status: Time Limit Exceeded

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_dict = dict()
for pattern in all_patterns:
    dp_dict[pattern] = 1e+10
dp_dict["0"*n] = 0

#%%

for j in range(m):
    for key in dp_dict.keys():    
        if dp_dict[key]+ab[j][0] < dp_dict[format(int(key,2)|int(keys[j],2),"0"+str(n)+"b")]:
            dp_dict[format(int(key,2)|int(keys[j],2),"0"+str(n)+"b")] = dp_dict[key]+ab[j][0]

if dp_dict["1"*n] != 1e+10:
    print(dp_dict["1"*n])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
key=[[] for _ in range(M)]
for i in range(M):
  A,B=map(int,input().split())
  key[i].append(A)
  C=list(map(int,input().split()))
  bit=0
  for c in C:
    bit+=2**(c-1)
  key[i].append(bit)

dp=[float("inf")]*(2**N)
dp[0]=0
ndp=[0]*(2**N)
for i in range(M):
  cost=key[i][0]
  bit=key[i][1]
  ndp=dp[:]
  for j in range(2**N):
  	ndp[bit|j]=min(dp[j]+cost,ndp[bit|j])
  dp=ndp[:]
 
print(dp[-1] if dp[-1]!=float("inf") else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    n,m = map(int,input().split())
    dp = [[10**10 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()))
        S = 0
        for j in range(b):
            x = pow(2,c[j]-1)
            S |= x
        for j in range(2**n):
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        for j in range(2**n):
            dp[i+1][j|S] = min(dp[i+1][j|S],dp[i][j]+a)
    if dp[m][2**n-1] == 10**10:
        print(-1)
    else:
        print(dp[m][2**n-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,m = map(int,input().split())
    dp = [[10**10 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()))
        S = 0
        for j in range(b):
            x = pow(2,c[j]-1)
            S |= x
        for j in range(2**n):
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
        for j in range(2**n):
            dp[i+1][j|S] = min(dp[i+1][j|S],dp[i][j]+a)
    if dp[m][2**n-1] == 10**10:
        print(-1)
    else:
        print(dp[m][2**n-1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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])

dp = [float('inf')]*int(2**n+1)
dp[0] = 0
for i in range(2**n):
    for j in range(m):
        s = i|kagi[j][1]
        # print(s)
        dp[s] = min(dp[s],dp[i] + kagi[j][0])
if dp[2**n-1] == float('inf'):
    print(-1)
else:
    print(dp[2**n-1])

Submission status: Time Limit Exceeded

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 + 1)
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: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
dp = [float("inf")]*(1<<n)
dp[0]=0
kagi = []
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    kagi.append([a,b,c])
for j in range(m):
    for i in range(1<<n):
        if dp[i] == -1:
            continue
        tmp = i+0
        for k in kagi[j][2]:
            tmp = tmp | 1<<(k-1)
        dp[tmp] = min(dp[tmp],dp[i]+kagi[j][0])
print(dp[(1<<n)-1] if dp[(1<<n)-1] != float("inf") else -1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
dp = [float("inf")]*(1<<n)
dp[0]=0
kagi = []
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    kagi.append([a,b,c])
for j in range(m):
    for i in range(1<<n):
        tmp = i+0
        for k in kagi[j][2]:
            tmp = tmp | 1<<(k-1)
        dp[tmp] = min(dp[tmp],dp[i]+kagi[j][0])
print(dp[(1<<n)-1] if dp[(1<<n)-1] != float("inf") else -1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
dp = [2**63]*4096
dp[0] = 0
for i in range(m):
  a,b = map(int,input().split())
  mask = 0
  c = list(map(int,input().split()))
  for i in c:
    mask |= ( 1 << i-1 )
  nxtdp = dp[:]
  for j in range(1 << n):
    if (j | mask) != j: continue
    for k in range(1 << n):
      if j == (k | mask):
        nxtdp[j] = min(nxtdp[j], dp[k] + a)
  dp = nxtdp
print(dp[(1<<n)-1] if dp[(1<<n)-1] < 2**63 else -1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n,m=map(int,readline().split())
    a=[0]*m
    b=[0]*m
    c=[0]*m
    for i in range(m):
        a[i],b[i]=map(int,readline().split())
        li=list(map(int,readline().split()))
        for j in range(len(li)):
            c[i]|=1<<(li[j]-1)

    inf=10**9
    dp=[[inf]*(1<<n) for _ in range(m+1)]
    dp[0][0]=0
    for i in range(1,m+1):
        for j in range(1<<n):
            #i番目の鍵を使わない
            dp[i][j]=min(dp[i-1][j],dp[i][j])

            #i番目の鍵を使う
            dp[i][j|c[i-1]]=min(dp[i][j|c[i-1]],dp[i-1][j]+a[i-1])

    ans=dp[m][(1<<n)-1]
    print(ans if ans<inf else -1)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
up=float('inf')
dp=[[up]*(1<<n) for i in range(m)]

dp[0][0]=0
buy=[]
a=[]
b=[]
for cnt in range(m):
    x,y=map(int,input().split())
    a.append(x)
    b.append(y)
    c=list(map(int,input().split()))
    tmp=0
    for w in c:
        tmp+=1<<(w-1)
    buy.append(tmp)

for i in range(m-1):
    for j in range(1<<n):
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        dp[i+1][j|buy[i]]=min(dp[i][j]+a[i],dp[i+1][j|buy[i]])

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

Submission status: Time Limit Exceeded

Solution code:
INF=10**18
N,M=map(int,input().split())

a,c=[],[]
for i in range(M):
    A,B=map(int,input().split())  
    C=list(map(int,input().split()))
    tmp=0
    for j in range(B):
      tmp+=1<<(C[j]-1)
    a.append(A)
    c.append(tmp)
    
dp=[[INF]*(1<<N) for i in range(M+1)]
dp[0][0]=0
for i in range(M):
    for j in range(1<<N):
        dp[i+1][j]=min(dp[i+1][j],dp[i][j])
        o=(j | c[i])
        dp[i+1][o]=min(dp[i+1][o],dp[i][j]+a[i])
ans=dp[M][2**N-1]
print(ans if ans!=INF else -1)

Submission status: Time Limit Exceeded

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


def pack(C):
    bitmask = 0
    for c in C:
        d = 1 << (c-1)
        bitmask |= d
    return bitmask


def read():
    N, M = list(map(int, input().strip().split()))
    A = list()
    C = list()
    for i in range(M):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        c = map(int, input().strip().split())
        C.append(pack(c))
    return N, M, A, C


def solve(N, M, A, C, INF=10**9):
    # dp[state][i]: i本の鍵[0, i)を使って状態stateにするための最小コスト
    n_states = 1 << N
    end_state = n_states - 1
    dp = [[INF for j in range(2)] for state in range(n_states)]
    dp[0][0] = 0
    dp[0][1] = 0

    for j in range(M):
        m0 = j & 1
        m1 = 1 - m0
        for state in range(n_states):
            next_state = state | C[j]
            dp[state][m1] = min(dp[state][m1], dp[state][m0])
            if next_state > state:
                dp[next_state][m1] = min(dp[next_state][m1], dp[state][m0] + A[j])
    
    m0 = M & 1
    return dp[end_state][m0] if dp[end_state][m0] != INF else -1


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Time Limit Exceeded

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


def pack(C):
    bitmask = 0
    for c in C:
        d = 1 << (c-1)
        bitmask |= d
    return bitmask


def read():
    N, M = list(map(int, input().strip().split()))
    A = list()
    C = list()
    for i in range(M):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        c = map(int, input().strip().split())
        C.append(pack(c))
    return N, M, A, C


def solve(N, M, A, C, INF=10**9):
    # dp[state][i]: i本の鍵[0, i)を使って状態stateにするための最小コスト
    n_states = 1 << N
    end_state = n_states - 1
    dp = [[INF for j in range(M+1)] for state in range(n_states)]
    for j in range(M+1):
        dp[0][j] = 0

    for j in range(M):
        for state in range(n_states):
            next_state = state | C[j]
            dp[state][j+1] = min(dp[state][j+1], dp[state][j])
            if next_state > state:
                dp[next_state][j+1] = min(dp[next_state][j+1], dp[state][j] + A[j])
    
    min_cost = INF
    for j in range(M):
        min_cost = min(min_cost, dp[end_state][j])
    return min_cost if min_cost != INF else -1


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Time Limit Exceeded

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


def pack(C):
    bitmask = 0
    for c in C:
        d = 1 << (c-1)
        bitmask |= d
    return bitmask


def read():
    N, M = list(map(int, input().strip().split()))
    A = list()
    C = list()
    for i in range(M):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        c = map(int, input().strip().split())
        C.append(pack(c))
    return N, M, A, C


def solve(N, M, A, C, INF=10**9):
    cost = [INF] * (2 << N)
    used = [False for i in range(M)]
    end = (1 << N) - 1
    
    def dfs(state):
        if state == end:
            return
        for i in range(M):
            ns = state | C[i]
            if not used[i] and state < ns:
                new_cost = cost[state] + A[i]
                if new_cost < cost[ns]:
                    cost[ns] = new_cost
                    used[i] = True
                    dfs(ns)
                    used[i] = False
        return cost

    cost[0] = 0
    dfs(0)
    return cost[end] if cost[end] != INF else -1


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Time Limit Exceeded

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


def pack(C):
    bitmask = 0
    for c in C:
        d = 1 << (c-1)
        bitmask |= d
    return bitmask


def read():
    N, M = list(map(int, input().strip().split()))
    A = list()
    C = list()
    for i in range(M):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        c = map(int, input().strip().split())
        C.append(pack(c))
    return N, M, A, C


def solve(N, M, A, C, INF=10**9):
    cost = [INF] * (2 << N)
    used = [False for i in range(M)]
    end = (1 << N) - 1
    
    def dfs(state):
        if state == end:
            return
        for i in range(M):
            ns = state | C[i]
            if not used[i] and state < ns:
                cost[ns] = min(cost[ns], cost[state] + A[i])
                used[i] = True
                dfs(ns)
                used[i] = False
        return cost

    cost[0] = 0
    dfs(0)
    return cost[end] if cost[end] != INF else -1


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))