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:
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

L = [[int(v) for v in input().split()] for _ in range(M * 2)]

ans = 10 ** 18
for i in range(1 << M):
    a = []
    for j in range(M):
        if (i >> j) & 1:
            a.append(j)

    s = set()
    p = 0
    for v in a:
        s = s | set(L[v * 2 + 1])
        p += L[v * 2][0]

    if len(s) != N:
        continue

    ans = min(ans, p)

if ans == 10 ** 18:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
abl = []
for _ in range(m):
   a,b = map(int,input().split())
   cl = list(map(int,input().split()))
   bit = 0
   for c in cl:
      bit += 2**(c-1)
   abl.append((a,bit))

bitdp = [[float('inf') for i in range(1<<n)] for i in range(m+1)]
   
bitdp[0][0] = 0

for i in range(m):
   for j in range(1<<n):
      bitdp[i+1][j] = min(bitdp[i][j], bitdp[i+1][j])
      bitdp[i+1][j|abl[i][1]] = min(bitdp[i][j] + abl[i][0], bitdp[i][j|abl[i][1]], bitdp[i+1][j|abl[i][1]])

if bitdp[-1][(1<<n)-1] == float('inf'):
   print(-1)
else:
   print(bitdp[-1][(1<<n)-1])

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
abl = []
for _ in range(m):
   a,b = map(int,input().split())
   cl = list(map(int,input().split()))
   bit = 0
   for c in cl:
      bit += 2**(c-1)
   abl.append((a,bit))


ans = float("inf")
for i in range(2 ** m):
   bit = [0] * m
   for j in range(m):
       if ((i >> j) & 1):
           bit[j] = 1
   state = 0
   tmp = 0
   for j in range(m):
      if bit[j] == 1:
         state |= abl[j][1]
         tmp += abl[j][0]
   if state == (1 << n) - 1:
      ans = min(ans, tmp)

if ans == float("inf"):
   print(-1)
else:
   print(ans)

Submission status: Time Limit Exceeded

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

cost = []
open = []
for i in range(m):
    a, b = map(int, input().split())
    c = set(list(map(int, input().split())))
    cost.append(a)
    open.append(c)

dp = [10**7] * (2**n)
dp[0] = 0
for i in range(m):
    key = []
    for j in range(1, n+1):
        if j in open[i]:
            key.append("1")
        else:
            key.append("0")
    key = "".join(key)
    key = int(key, 2)
    for j in range(2**n):
        next = j | key
        dp[next] = min(dp[next], dp[j] + cost[i])

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[]
c=[]

for i in range(m):
    ab.append(list(map(int,input().split())))
    c.append(list(map(int,input().split())))
    
for i in range(m):
    temp=0
    for j in range(len(c[i])):
        temp+=2**(c[i][j]-1)
    c[i]=temp
    #c[i]=(("0"*n)+bin(temp)[2:])[-n:]
   
dp=dict()

for i in range(2**n):
    dp[i]=10**9
    #dp[(("0"*n)+bin(i)[2:])[-n:]]=-1
    
dp[0]=0
    
#print(dp)
for i in range(m):
    for k,item in dp.items():
        dp[c[i]|k]=min(dp[c[i]|k],dp[k]+ab[i][0])

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

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
lv=[]
lk=[]
for i in range(m):
  a,b=map(int,input().split())
  l=list(map(int,input().split()))
  lv.append(a)
  lk.append(l)
ans=[10**10]
def dfs(now,d,price):#どの鍵を採用していくか？
  b=True
  for i in d:
    if d[i]==0:
      b=False
  if b:
    ans[0]=min(ans[0],price)
    return
  if now==m:
    return
  dk=lk[now]
  b=False
  for i in dk:
    if d[i]==0:
      b=True
  if not b:
    dfs(now+1,d,price)
  else:
    dfs(now+1,d,price)
    d1=copy.deepcopy(d)
    for i in dk:
      d1[i]=1
    dfs(now+1,d1,price+lv[now])
d={}
for i in range(1,n+1):
  d[i]=0
dfs(0,d,0)
if ans[0]==10**10:
  print(-1)
else:
  print(ans[0])

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
lv=[]
lk=[]
for i in range(m):
  a,b=map(int,input().split())
  l=list(map(int,input().split()))
  lv.append(a)
  lk.append(l)
ans=[10**10]
def dfs(now,d,price):#どの鍵を採用していくか？
  b=True
  for i in d:
    if d[i]==0:
      b=False
  if b:
    ans[0]=min(ans[0],price)
    return
  if now==m:
    return
  dk=lk[now]
  b=False
  for i in dk:
    if d[i]==0:
      b=True
  if not b:
    dfs(now+1,d,price)
  else:
    dfs(now+1,d,price)
    d1=copy.deepcopy(d)
    for i in dk:
      d1[i]=1
    dfs(now+1,d1,price+lv[now])
d={}
for i in range(1,n+1):
  d[i]=0
dfs(0,d,0)
if ans[0]==10**10:
  print(-1)
else:
  print(ans[0])

Submission status: Time Limit Exceeded

Solution code:
INF = 10**8

N, M = map(int, input().split())
n = 2 ** N
dp = [0] + [INF]*(n - 1)

for _ in range(M):
  a, b = map(int, input().split())
  c = sum(map(lambda x:2**(x-1), list(map(int, input().split()))))
  for i in range(n):
    dp[i | c] = min(dp[i] + a, dp[i | c])
  
if dp[-1] == INF:
  print(-1)
else:
  print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
INF = 1001001001

N, M = map(int, input().split())
key = []
for i in range(M):
    a, b = map(int, input().split())
    s = 0
    c = list(map(int, input().split()))
    for j in range(b):
        c[j] -= 1
        s |= 1<<c[j]
    key.append([s, a])
dp = [INF] * (1<<N)
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = s | key[i][0]
        cost = dp[s] + key[i][1]
        dp[t] = min(dp[t], cost)
ans = dp[-1]
if ans == INF:
    ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n , m = map(int, input().split())
keys = deque()
def trans(k):
    res = [0 for i in range(n)]
    for i in k:
        res[-i] = 1
    res = int("".join(map(str, res)), 2)
    return res

for i in range(m):
    a, b = list(map(int, input().split()))
    c = deque(list(map(int, input().split())))
    c.appendleft(a)
    keys.append(c)
inf = 10 ** 8
dp = [inf for i in range(2**n)]
dp[0] = 0
for i in range(m):
    key_value = keys[i].popleft()
    can_open = keys[i]
    for j in range(2**n):
        next = j | trans(can_open)
        dp[next] = min(dp[next], dp[j] + key_value)
#print(dp)
if dp[-1] >= inf:
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n , m = map(int, input().split())
keys = []
def trans(k):
    res = [0 for i in range(n)]
    for i in k:
        res[-i] = 1
    res = int("".join(map(str, res)), 2)
    return res

for i in range(m):
    a, b = list(map(int, input().split()))
    c = list(map(int, input().split()))
    keys.append([a] + c)
inf = 10 ** 10
dp = [inf for i in range(2**n)]
dp[0] = 0
for i in range(m):
    key_value = keys[i-1][0]
    can_open = keys[i-1][1:]
    for j in range(2**n):
        next = j | trans(can_open)
        dp[next] = min(dp[next], dp[j] + key_value)
#print(dp)
if dp[-1] >= inf:
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import math
    N,M=map(int,input().split())
    a=[]
    for i in range(M):
        tmp=list(map(int,input().split()))
        tmpc=list(map(int,input().split()))
        c=0
        for j in range(len(tmpc)):
            c+=2**(tmpc[j]-1)
        tmp[1]=c
        a+=[tmp]


    dp=[[10**10 for j in range(2**N)] for i in range(M)]
    dp[0][0]=0
    dp[0][a[0][1]]=a[0][0]


    for i in range(1,M):
        dp[i]=dp[i-1]
        for j in range(2**N):
            z,p=a[i][0],a[i][1]
            q=j|p
            dp[i][q]=min(dp[i-1][j]+z,dp[i][q])

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


for i in range(M):
    a, _ = map(int, input().split())
    key=sum([2**(int(i)-1) for i in input().split()])
    for j in range(L):
            q=j|key
            dp[q]=min(dp[j]+a,dp[q])


ans=dp[L-1]
print(ans if ans<10**10 else -1)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy
N,M=map(int,input().split())
a=[]
for i in range(M):
    tmp=list(map(int,input().split()))
    tmpc=list(map(int,input().split()))
    c=0
    for j in range(len(tmpc)):
        c+=2**(tmpc[j]-1)
    tmp[1]=c
    a+=[tmp]


dp=[[10**10 for j in range(2**N)] for i in range(M)]
dp[0][0]=0
dp[0][a[0][1]]=a[0][0]


for i in range(1,M):
    dp[i]=dp[i-1]
    for j in range(2**N):
        if dp[i-1][j]<10**10:
            q=j|a[i][1]
            dp[i][q]=min(dp[i-1][j]+a[i][0],dp[i][q])

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

Submission status: Time Limit Exceeded

Solution code:
import math
N,M=map(int,input().split())
a=[]
for i in range(M):
    tmp=list(map(int,input().split()))
    tmpc=list(map(int,input().split()))
    c=0
    for j in range(len(tmpc)):
        c+=2**(tmpc[j]-1)
    tmp[1]=c
    a+=[tmp]


dp=[[10**10 for j in range(2**N)] for i in range(M)]
dp[0][0]=0
dp[0][a[0][1]]=a[0][0]


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

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

Submission status: Time Limit Exceeded

Solution code:
import math
N,M=map(int,input().split())
a=[]
for i in range(M):
    tmp=list(map(int,input().split()))
    tmpc=list(map(int,input().split()))
    c=0
    for j in range(len(tmpc)):
        c+=2**(tmpc[j]-1)
    tmp[1]=c
    a+=[tmp]


dp=[[10**10 for j in range(2**N)] for i in range(M)]
dp[0][0]=0
dp[0][a[0][1]]=a[0][0]


for i in range(1,M):
    dp[i]=dp[i-1]
    for j in range(2**N):
        z,p=a[i][0],a[i][1]
        q=j|p
        dp[i][q]=min(dp[i-1][j]+z,dp[i][q])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
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 = 0
  for j in list(map(int, input().split())):
    c += 1<<(j-1)
  
  for k in range(1<<n):
    dp[k|c] = min(dp[k|c], dp[k]+a)
    
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])

Submission status: Time Limit Exceeded

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

n1 = 2 ** N
dp = [[120001 for i in range(n1)] for j in range(M + 1)]
dp[0][0] = 0

for i in range(M):
  dp_i = dp[i]
  dp_i1 = dp[i + 1]
  key = key_list[i]

  for j in range(n1):
    dp_key = dp_i[j]
    dp_i1[j] = min(dp_key, dp_i1[j])
    dp_i1[j | key[1]] = min(dp_key + key[0], dp_i1[j | key[1]])
  # print(dp)
ans = dp[M - 1][n1 - 1]
if ans == 120001:
  print(-1)
else:
  print(dp[M - 1][n1 - 1])

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[]
k=[]
for _ in range(m):
  a.append(list(map(int,input().split()))[0])
  k.append(sum(2**(int(i)-1)for i in input().split()))
inf=float('inf')
dp=2**n*[inf]
dp[0]=0
for i in range(2**n):
  for j in range(m):
    dp[i|k[j]]=min(dp[i|k[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())
l = []
for i in range(m):
    a,b = map(int,input().split())
    c = 0
    for j in map(int,input().split()):
        c += (1<<(j-1))
    l.append((c,a))

dp = dict()
tmp = [(0,0)]
while tmp != []:
    tmp2 = []
    for i in tmp:
        for j in l:
            if j[0] | i[0] != i[0]:
                ctmp = (j[0] | i[0] ,i[1] + j[1])
                if dp.get(ctmp[0],-1) == -1:
                    dp[ctmp[0]] = ctmp[1]
                    if ctmp[0] != 2**n - 1:
                        tmp2.append(ctmp)
                else:
                    if dp[ctmp[0]] > ctmp[1]:
                        dp[ctmp[0]] = ctmp[1]
                        if ctmp[0] != 2**n - 1:
                            tmp2.append(ctmp)                
    tmp = tmp2

print(dp.get(2**n-1,-1))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
l = []
for i in range(m):
    a,b = map(int,input().split())
    c = 0
    for j in map(int,input().split()):
        c += (1<<(j-1))
    l.append((c,a))

dp = dict()
tmp = [(0,0)]
while tmp != []:
    tmp2 = []
    for i in tmp:
        for j in l:
            if j[0] | i[0] != i[0]:
                ctmp = (j[0] | i[0] ,i[1] + j[1])
                if dp.get(ctmp[0],-1) == -1:
                    dp[ctmp[0]] = ctmp[1]
                    if ctmp[0] != 2**n - 1:
                        tmp2.append(ctmp)
                else:
                    if dp[ctmp[0]] > ctmp[1]:
                        dp[ctmp[0]] = ctmp[1]
                    if ctmp[0] != 2**n - 1:
                        tmp2.append(ctmp)
    tmp = tmp2

print(dp.get(2**n-1,-1))

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())

inf = float('inf')
p = 2**n
dp = [inf]*p
dp[0] = 0

for _ in range(m):
    a, _ = map(int, input().split())
    c = sum([2**(int(i)-1) for i in list(input().split())])
    for i in range(p):
        dp[i|c] = min(dp[i|c], dp[i] + a)
    
if dp[-1] == inf:
    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())

inf = float('inf')
p = 2**n
dp = [inf]*p
dp[0] = 0

for _ in range(m):
    a, _ = map(int, input().split())
    c = sum([2**(i-1) for i in map(int, input().split())])
    for i in range(p):
        dp[i|c] = min(dp[i|c], dp[i] + a)
    
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
 
n,m = map(int,input().split())
a_arr = []
b_arr = []
c_arr = []
 
dic = {i:sys.maxsize for i in range(2 ** n)}
dic[0] = 0
 
for i in range(m):
  a,b = map(int,input().split())
  tmp_arr = list(map(int, input().split()))
  
  arr = []
  for j in range(1, n+1):
    if j in tmp_arr:
      arr.append('1')
    else:
      arr.append('0')
  
  c = int(''.join(arr),2)
  
  dic2 = dic.copy()
  
  for k,v in dic.items():
    dic2[k|c] = min(dic2[k|c],a+v)
    
  dic = dic2
 
if dic[(2**n)-1] != sys.maxsize:
  print(dic[(2**n) -1])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
n,m = map(int,input().split())
a_arr = []
b_arr = []
c_arr = []
 
dic_arr = [{i:sys.maxsize for i in range(2 ** n)}]
dic_arr[0][0] = 0
 
for i in range(m):
  a,b = map(int,input().split())
  a_arr.append(a)
  b_arr.append(b)
  tmp_arr = list(map(int, input().split()))
  
  arr = []
  for j in range(1, n+1):
    if j in tmp_arr:
      arr.append('1')
    else:
      arr.append('0')
  
  c = int(''.join(arr),2)
  
  dic_arr.append(dic_arr[i].copy())
  
  for k in dic_arr[i].keys():
    dic_arr[i+1][k|c] = min(dic_arr[i+1][k|c],a+dic_arr[i][k])  
 
if dic_arr[m][(2**n)-1] != sys.maxsize:
  print(dic_arr[m][(2**n) -1])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
n,m = map(int,input().split())
a_arr = []
b_arr = []
c_arr = []
 
dic_arr = [{i:sys.maxsize for i in range(2 ** n)}]
dic_arr[0][0] = 0
 
for i in range(m):
  a,b = map(int,input().split())
  a_arr.append(a)
  b_arr.append(b)
  tmp_arr = list(map(int, input().split()))
  
  arr = []
  for j in range(1, n+1):
    if j in tmp_arr:
      arr.append('1')
    else:
      arr.append('0')
  
  c = int(''.join(arr),2)
  
  dic_arr.append(dic_arr[i].copy())
  
  for k,v in dic_arr[i].items():
    dic_arr[i+1][k|c] = min(dic_arr[i+1][k|c],a+v)  
 
if dic_arr[m][(2**n)-1] != sys.maxsize:
  print(dic_arr[m][(2**n) -1])
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

n,m = map(int,input().split())
a_arr = []
b_arr = []
c_arr = []

dic_arr = [{i:sys.maxsize for i in range(2 ** n)}]
dic_arr[0][0] = 0

for i in range(m):
  a,b = map(int,input().split())
  a_arr.append(a)
  b_arr.append(b)
  tmp_arr = list(map(int, input().split()))
  
  arr = []
  for i in range(1, n+1):
    if i in tmp_arr:
      arr.append('1')
    else:
      arr.append('0')
  
  c_arr.append(int(''.join(arr),2))

for i in range(m):
  a = a_arr[i]
  b = b_arr[i]
  c = c_arr[i]
  
  dic_arr.append(dic_arr[i].copy())
  
  for k,v in dic_arr[i].items():
    dic_arr[i+1][k|c] = min(dic_arr[i+1][k|c],a+v)

if dic_arr[m][(2**n)-1] != sys.maxsize:
  print(dic_arr[m][(2**n) -1])
else:
  print(-1)

Submission status: Time Limit Exceeded

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

f=[10**7 for x in range(2**n)]
l=[]

for i in range(m):
  a,b = map(int,input().split())
  c = [int(x) for x in input().split()]
  s = 0
  for j in c:
    s += 2**(j-1)
  f[s]=min(f[s],a)

for i in range(2**n):
  if f[i] != 10**7:
    l.append([i,f[i]])

v=[[10**7 for x in range(2**n)] for y in range(2)]
v[0][0]=0

i=0
for s,a in l:
  for j in range(2**n):
    v[(i+1)%2][j] = v[i%2][j]
  for j in range(2**n):
    if v[i%2][j] != 10**7:
      v[(i+1)%2][j|s] = min(v[(i+1)%2][j|s], v[i%2][j]+a)
  i+=1

print(v[i%2][2**n-1] if v[i%2][2**n-1] != 10**7 else -1)

Submission status: Time Limit Exceeded

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

l=[]

for i in range(m):
  a,b = map(int,input().split())
  c = [int(x) for x in input().split()]
  s = 0
  for j in c:
    s += 2**(j-1)
  l.append([s,a])

#print(l)

v=[[10**7 for x in range(2**n)] for y in range(2)]
v[0][0]=0

i=0
for s,a in l:
  for j in range(2**n):
    v[(i+1)%2][j] = v[i%2][j]
  for j in range(2**n):
    if v[i%2][j] != 10**7:
      v[(i+1)%2][j|s] = min(v[(i+1)%2][j|s], v[i%2][j]+a)
  i+=1

print(v[(i+1)%2][2**n-1] if v[(i+1)%2][2**n-1] != 10**7 else -1)

Submission status: Time Limit Exceeded

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

l = []

for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    bit_c = 0
    for x in c:
        bit_c = bit_c | (1<<(x-1))
    l.append([a,bit_c])


ans = 10**9

for i in range(2 ** m):
    cost = 0
    chk = 0
    for j in range(m):
        if ((i>>j) &1):
            cost += l[j][0]
            chk = chk | l[j][1]
    if chk == 2**n-1:
        ans = min(ans,cost)

if ans == 10**9:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

l=[[] for x in range(n)]
v=[[10**7 for x in range(2**n)] for y in range(2)]
v[0][0]=0

#print(v)
for i in range(m):
  a,b = map(int,input().split())
  c = [int(x) for x in input().split()]
  s = 0
  for j in c:
    s += 2**(j-1)
  for j in c:
    l[j-1].append([a,s])

for i in range(n):
  for j in range(2**n):
    v[(i+1)%2][j] = v[i%2][j]
  for j in range(2**n):
    for k in l[i]:
      if v[i%2][j] != 10**7:
          v[(i+1)%2][j|k[1]] = min(v[(i+1)%2][j|k[1]], v[i%2][j]+k[0])

print(v[(i+1)%2][2**n-1] if v[(i+1)%2][2**n-1] != 10**7 else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, m = [int(i) for i in input().split()]
costs = []
boxes = []

for i in range(m):
    c, bi = [int(i) for i in input().split()]
    costs.append(c)    
    box = [int(k)-1 for k in input().split()]
    boxes.append(box)

dp = [[-1 for i in range(5000)] for j in range(m+5)]

def f(idx, mask):
    '''
    at key idx, mask stores
    the current boxes i already have

    returns the min cost to get this
    '''
    if mask == (1<<n)-1:
        return 0
    if idx == m:
        return 10**18
    if dp[idx][mask] != -1:
        return dp[idx][mask]
    ans = f(idx+1, mask)
    isnew = 0
    curkeymask = 0
    for possiblebox in boxes[idx]:
        curkeymask |= (1<<possiblebox)

    ans = min(ans, costs[idx]+f(idx+1, mask|curkeymask))
    dp[idx][mask] = ans
    return ans

for mask in range((1<<n)-1, -1, -1):
    for idx in range(m, -1, -1):
        if mask == (1<<n)-1:
            dp[idx][mask] = 0
            continue
        if idx == m:
            dp[idx][mask] = 10**18
            continue
        dp[idx][mask] = dp[idx+1][mask]
        cur = 0
        for poss in boxes[idx]:
            cur |= (1<<poss)
        dp[idx][mask] = min(dp[idx][mask], dp[idx+1][mask|cur] + costs[idx])

ans = f(0, 0)
if ans == 10**18:
    print(-1)
else:
    print(f(0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, m = [int(i) for i in input().split()]
costs = []
boxes = []

for i in range(m):
    c, bi = [int(i) for i in input().split()]
    costs.append(c)    
    box = [int(k)-1 for k in input().split()]
    boxes.append(box)

dp = [[-1 for i in range(9025)] for j in range(m+5)]


for mask in range((1<<n)-1, -1, -1):
    for idx in range(m, -1, -1):
        if mask == (1<<n)-1:
            dp[idx][mask] = 0
            continue
        if idx == m:
            dp[idx][mask] = 10**18
            continue
        dp[idx][mask] = dp[idx+1][mask]
        cur = 0
        for poss in boxes[idx]:
            cur |= (1<<poss)
        dp[idx][mask] = min(dp[idx][mask], dp[idx+1][mask|cur] + costs[idx])

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from functools import lru_cache
import sys


def solve(*args: str) -> str:
    n, m = map(int, args[0].split())

    keys = list(zip(
        list(map(lambda _: int(_.split()[0]), args[1::2])),
        map(
            lambda _: set2bin(
                set(map(int, _.split())),
                n, start=1
            ), args[2::2])
    ))
    dp = DP(keys, n, 12*10**5)
    sys.setrecursionlimit(2**31-1)
    ret = dp.search_min_cost(0, 0)

    return str(-1 if 12*10**5 < ret else ret)


class DP:
    def __init__(self, keys: list, n: int, max: int):
        self._keys = keys
        self._mask = int('1'*n, 2)
        self._max = 1+max

    @lru_cache(maxsize=None)
    def search_min_cost(self, index: int, unlocked: int) -> int:
        ret = 0

        if len(self._keys) == index:
            if unlocked != self._mask:
                ret = self._max

        else:
            a, C = self._keys[index]
            ret = min(
                a+self.search_min_cost(index+1, C | unlocked),
                self.search_min_cost(index+1, unlocked)
            )

        return ret


def set2bin(S: set, n: int, start: int = 0) -> int:
    ret = 0
    for s in S:
        ret += 2**(s-start)
    return ret


def bin2int(B: list) -> int:
    ret = 0
    for n in range(len(B)):
        if B[n]:
            ret += 2**n

    return ret


if __name__ == "__main__":
    nm = input()
    _, m = map(int, nm.split())
    print(solve(*([nm]+[input() for _ in range(2*m)])))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
inf = 1e9
dp = [inf] * (1 << n)
dp[0] = 0
for _ in range(m):
  a, b = map(int, input().split())
  cs = list(map(int, input().split()))
  r = 0
  for c in cs:
    r |= 1 << (c - 1)
    for i in range(1 << n):
      if dp[i | r] > dp[i] + a:
        dp[i | r] = dp[i] + a
      
if dp[(1 << n) - 1] == inf:
  print("-1")
else:
  print("{}".format(dp[(1 << n) - 1]))

Submission status: Time Limit Exceeded

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    abl = []
    cl = []
    for i in range(m):
        abl.append(list(map(int, input().rstrip('\n').split())))
        cl.append(list(map(int, input().rstrip('\n').split())))
    dp = [[set(), 0] for _ in range(2 ** m)]
    mt = 10 ** 20
    #各bitを総検索
    for i in range(2 ** m):
        bt = bin(i)
        #先頭bitに対して処理
        if i >= 1 and len(bt[2:]) - 1 < m:
            for c in cl[len(bt[2:])-1]:
                dp[i][0].add(c)
            dp[i][1] += abl[len(bt[2:])-1][0]
        #先頭bitより後ろのbitが同じパターンの解放済とコストを追加
        if i >= 2:
            for c in dp[int(bt[3:], 2)][0]:
                dp[i][0].add(c)
            dp[i][1] += dp[int(bt[3:], 2)][1]
        if len(dp[i][0]) == n:
            mt = min(mt, dp[i][1])
    print(mt if mt != 10 ** 20 else -1)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
# M: 鍵の数
# N: 宝箱の数(制限値になる)
# openable: 開けられる宝箱のリスト
# price: 鍵の価格

def power(n):
    if n == 0:
        return [[]]
    else:
        l = []
        for i in power(n-1):
            k = i + [n]
            l.append(k)
        return power(n-1) + l

def abc142e(M, N, price, openable):
    # dp initialize
    inf = float("inf")
    dp = [[inf for j in range((2**N)+1)] for i in range(M+10)]
    for i in range(M+10):
        dp[i][0] = 0
    closed_boxes = power(N)
    # dp
    for i in range(M):
        if openable[i] not in closed_boxes:
            dp[i][j] = inf
        else:
            for j in range(len(closed_boxes)):
                l = list(set(closed_boxes[j])-set(openable[i]))
                l.sort()
                dp[i+1][j] = min(dp[i][closed_boxes.index(l)]+price[i], dp[i][j])
    if dp[M][2**N-1] == inf: return -1
    else: return dp[M][2**N-1]

if __name__ == "__main__":
    N,M = map(int, input().split())
    price = []
    openable = []
    for i in range(M):
        a,b = map(int, input().split())
        c = [i for i in map(int, input().split())]
        price.append(a)
        openable.append(c)

    print(abc142e(M, N, price, openable))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
dp = [INF]*(1<<N)
dp[0] = 0

for _ in range(M):
	a, b = MAP()
	c = LIST()
	d = 0
	for x in c:
		d += 1<<(x-1)

	for j in range(1<<N):
		tmp = j|d
		dp[tmp] = min(dp[tmp], dp[j]+a)

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

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
a = [0] * M
b = [0] * M
d = [0] * M

for i in range(M):
	a[i], b[i] = MAP()
	c = LIST()
	for x in c:
		d[i] += 1<<(x-1)

dp = [INF]*(1<<N)
dp[0] = 0
for i in range(1, M+1):
	for j in range(1<<N):
		dp[j|d[i-1]] = min(dp[j|d[i-1]], dp[j]+a[i-1])

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
dp = [ [float("inf")]*(2**n) for _ in range(m) ]
dp[0][0] = 0
for i in range(1, m):
  a, b = map(int, input().split())
  k = set(map(int, input().split()))
  c = 0
  for l in k:
    c += 2**(l-1)
  for j in range(2**n):
    dp[i][j] = min(dp[i-1][j&(~c)]+a, dp[i-1][j])

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

Submission status: Time Limit Exceeded

Solution code:
n, m = list(map(lambda x:int(x), input().split()))
 
key_list = {}
 
for i in range(m):
    key_price, _ = list(map(lambda x:int(x), input().split()))
    open_list = list(map(lambda x:int(x), input().split()))
    key_list[i] = [key_price, open_list]
    
situation_val = 1 << n
 
dp = [[float('INF')] * situation_val for i in range(m+1)]
for i in range(m+1):
    dp[i][0] = 0
 
for i in range(m):
    price = key_list[i][0]
    treasure = key_list[i][1]
    key_val = 0
    for v in treasure:
        key_val += (1 << v-1)
        
    for j in range(situation_val):
        key_used_situation = j | key_val
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        dp[i+1][key_used_situation] = min(dp[i+1][key_used_situation], dp[i][j]+price)
        
        
ans = dp[m][situation_val-1]

if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(opened, res):
  global ans
  for i in range(1, N+1):
    if str(i) not in opened:
      for x in data[i]:
        tami(opened + " ".join(map(str, KeyID[x])), res + Value[x])
      break
  else:
    ans = min(ans, res)

N, M = IL()

KeyID = [[] for _ in range(M+1)]
data = [[] for _ in range(N+1)]
Value = [0 for _ in range(M+1)]
for i in range(1, M+1):
  a, b = IL()
  c = IL()

  KeyID[i].append(c)
  Value[i] = a
  for num in c:
    data[num].append(i)
#print(Value)
#print(KeyID)

ans = MAX_INT
tami("", 0)
if ans == MAX_INT:
  print(-1)
else:
  print(ans)