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:
#142e'' (高速化)
import random

N,M = map(int, input().split()) #N<=12,M<=10**3

openable_box_and_price = {} #開けられる箱のtaple:値段 なdict

#同じ箱を開けられる鍵は最安値のものを選びつつ、読み込み
for i in range(M): #10**3
    a,b = map(int, input().split())
    c = tuple(map(int, input().split()))
    
    if c in openable_box_and_price:
        if openable_box_and_price[c] > a:
            openable_box_and_price[c] = a
    else:
        openable_box_and_price[c] = a

#鍵に番号(0～)を付けるためlist化
index_list = [i for i in range(len(openable_box_and_price))]
key_price = dict(zip(index_list,openable_box_and_price.values()))
#key_price = list(openable_box_and_price.values())

key_openable_box = list(openable_box_and_price.keys())

#ある箱を開けられる鍵のリストを作る
box_and_openable_key = [[] for _ in range(N)]
key_number = 0

for openable_boxes in key_openable_box:  #10**3
    for openable_box in openable_boxes: #12
        box_and_openable_key[openable_box-1].append(key_number)

    key_number += 1

#そもそも開けられる鍵が無い箱があったら-1を出力
key_check = [len(openable_key) for openable_key in box_and_openable_key]
for number_of_key in key_check: #12
    if number_of_key == 0:
        print(-1)
        break
else:
    #すべての箱を開けられる鍵の組み合わせのうち、最安値を求める。
    cheapest_price = sum(key_price.values()) #仮として最高値(全ての鍵を用いた場合)を入れる。
    keys_and_sum_price = {} #高速化のためにメモする
    key_combination = []
    base_key_combination = []
    
    def get_price_of_cheap_key_combination(box_number,cheapest_price,key_combination):
        base_key_combination = key_combination

        for openable_key in random.sample(box_and_openable_key[box_number],len(box_and_openable_key[box_number])): #box_and_openable_key[box_number]:
            key_combination = base_key_combination + [openable_key]
            tuple_key_combination = tuple(set(key_combination))
            
            if tuple_key_combination not in keys_and_sum_price:
                if base_key_combination != []:
                    now_price = keys_and_sum_price[tuple(set(base_key_combination))] + key_price[openable_key]
                else:
                    now_price = key_price[openable_key]
                    
                keys_and_sum_price[tuple_key_combination] = now_price
            else:
                now_price = keys_and_sum_price[tuple_key_combination]
            
            if now_price < cheapest_price:
                #全部の箱に対して鍵を選択済みか
                if box_number == N-1: #Yes→価格比較
                    cheapest_price = now_price
                else: #No→再帰する
                    cheapest_price = get_price_of_cheap_key_combination(box_number+1,cheapest_price,key_combination)
            
        return cheapest_price
        
    print(get_price_of_cheap_key_combination(0,cheapest_price,key_combination))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = map(int, input().split())
inf = 10**9
dp = np.zeros((M + 1, 2**N), dtype = 'int') + inf 
# dp[i][j] := i個目までの鍵を使うときの状態jを実現する最小費用 # 0列目は使わない
# 行 : 0番目の鍵 ~ M - 1番目の鍵
# 列 : 状態0 ~ 2**N - 1

dp[0][0] = 0

for i in range(1, M + 1):
    a, b = map(int, input().split())
    c_ls = map(int, input().split())
    d = 0 # i番目の鍵が開けられる宝箱の状態
    for c in c_ls:
        d += 2**(c - 1)
    for j in range(2**N):
        jord = np.bitwise_or(j, d)
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        dp[i][jord] = min(dp[i - 1][j] + a, dp[i][jord])
#         if i == 1:
#             print(dp[i][jord], i, jord, j, d, np.bitwise_or(j, d))
        
if dp[M][2**N - 1] == inf:
    print(- 1)
else:
    print(dp[M][2**N - 1])

Submission status: Time Limit Exceeded

Solution code:
#A=int(input())
#A=list(map(int,(input().split())))
N,M=list(map(int,(input().split())))
A=[]
B=[]
C=[]
for x in range(M):
	te,mp=list(map(int,(input().split())))
	A.append(te)
	B.append(mp)
	temp=list(map(int,(input().split())))
	c=0
	for x in temp:
		c+=2**(x-1)
	C.append(c)
dp=[]
for x in range(M+1):
	dp.append([-1]*(2**N))
dp[0][0]=0

for i in range(M):
	for j in range(2**N):
		if (dp[i][j]>=0):
			#買わなかった場合
			if (dp[i+1][j]==-1):
				dp[i+1][j]=dp[i][j]
			else:
				dp[i+1][j]=min(dp[i+1][j],dp[i][j])
			#買った場合
			if (dp[i+1][j|C[i]]==-1):
				dp[i+1][j|C[i]]=dp[i][j]+A[i]
			else:
				dp[i+1][j|C[i]]=min(dp[i+1][j|C[i]],dp[i][j]+A[i])
"""
for x in dp:
	print(x)
print("\n",C)"""
print(dp[M][2**N-1])

Submission status: Time Limit Exceeded

Solution code:
#142e'' (高速化)
N,M = map(int, input().split()) #N<=12,M<=10**3

openable_box_and_price = {} #開けられる箱のtaple:値段 なdict

#同じ箱を開けられる鍵は最安値のものを選びつつ、読み込み
for i in range(M): #10**3
    a,b = map(int, input().split())
    c = tuple(map(int, input().split()))
    
    if c in openable_box_and_price:
        if openable_box_and_price[c] > a:
            openable_box_and_price[c] = a
    else:
        openable_box_and_price[c] = a

#鍵に番号(0～)を付けるためlist化
index_list = [i for i in range(len(openable_box_and_price))]
key_price = dict(zip(index_list,openable_box_and_price.values()))
#key_price = list(openable_box_and_price.values())

key_openable_box = list(openable_box_and_price.keys())

#ある箱を開けられる鍵のリストを作る
box_and_openable_key = [[] for _ in range(N)]
key_number = 0

for openable_boxes in key_openable_box:  #10**3
    for openable_box in openable_boxes: #12
        box_and_openable_key[openable_box-1].append(key_number)

    key_number += 1

#そもそも開けられる鍵が無い箱があったら-1を出力
key_check = [len(openable_key) for openable_key in box_and_openable_key]
for number_of_key in key_check: #12
    if number_of_key == 0:
        print(-1)
        break
else:
    #すべての箱を開けられる鍵の組み合わせのうち、最安値を求める。
    cheapest_price = sum(key_price.values()) #仮として最高値(全ての鍵を用いた場合)を入れる。
    keys_and_sum_price = {} #高速化のためにメモする
    key_combination = []
    base_key_combination = []
    
    def get_price_of_cheap_key_combination(box_number,cheapest_price,key_combination):
        base_key_combination = key_combination
        
        for openable_key in box_and_openable_key[box_number]:
            key_combination = base_key_combination + [openable_key]
            tuple_key_combination = tuple(set(key_combination))
            
            if tuple_key_combination not in keys_and_sum_price:
                if base_key_combination != []:
                    now_price = keys_and_sum_price[tuple(set(base_key_combination))] + key_price[openable_key]
                else:
                    now_price = key_price[openable_key]
                    
                keys_and_sum_price[tuple_key_combination] = now_price
            else:
                now_price = keys_and_sum_price[tuple_key_combination]
            
            if now_price < cheapest_price:
                #全部の箱に対して鍵を選択済みか
                if box_number == N-1: #Yes→価格比較
                    cheapest_price = now_price
                else: #No→再帰する
                    cheapest_price = get_price_of_cheap_key_combination(box_number+1,cheapest_price,key_combination)
            
        return cheapest_price
        
    print(get_price_of_cheap_key_combination(0,cheapest_price,key_combination))

Submission status: Time Limit Exceeded

Solution code:
#142e'' (高速化)
N,M = map(int, input().split()) #N<=12,M<=10**3

openable_box_and_price = {} #開けられる箱のtaple:値段 なdict

#同じ箱を開けられる鍵は最安値のものを選びつつ、読み込み
for i in range(M): #10**3
    a,b = map(int, input().split())
    c = tuple(map(int, input().split()))
    
    #print(c,":",a)
    
    if c in openable_box_and_price:
        #print("重複")
        if openable_box_and_price[c] > a:
            #print("安値更新")
            openable_box_and_price[c] = a
    else:
        openable_box_and_price[c] = a

#鍵に番号(0～)を付けるためlist化
key_price = list(openable_box_and_price.values())
key_openable_box = list(openable_box_and_price.keys())

#ある箱を開けられる鍵のリストを作る
box_and_openable_key = [[] for _ in range(N)]
key_number = 0

for openable_boxes in key_openable_box:  #10**3
    for openable_box in openable_boxes: #12
        box_and_openable_key[openable_box-1].append(key_number)

    key_number += 1

#print("########################")
#print(key_price)
#print(key_openable_box)    
#print(box_and_openable_key)
#print("########################")

#そもそも開けられる鍵が無い箱があったら-1を出力
for openable_key in box_and_openable_key:
    if not openable_key:
        print(-1)
        break
else:
    #すべての箱を開けられる鍵の組み合わせのうち、最安値を求める。
    cheapest_price = sum(key_price) #仮として最高値(全ての鍵を用いた場合)を入れる。
    keys_and_sum_price = {} #高速化のためにメモする
    key_combination = []
    base_key_combination = []
    #key_combination_append = base_key_combination.append #appendを外に出して高速化
    #key_combination_pop = key_combination.pop #popを外に出して高速化
    
    def get_price_of_cheap_key_combination(box_number,cheapest_price,key_combination):
        #print("箱:",box_number)
        base_key_combination = key_combination
        
        for openable_key in box_and_openable_key[box_number]:
            
            #箱に対する鍵を追加する
            key_combination = base_key_combination + [openable_key]
            #print(key_combination,":",end="")
            
            #値段を見る…dictにあったら省略
            tuple_key_combination = tuple(set(key_combination))
            
            if tuple_key_combination not in keys_and_sum_price:
                #print("新規計算")
                if base_key_combination != []:
                    now_price = keys_and_sum_price[tuple(set(base_key_combination))] + key_price[openable_key] #sum(key_price[i] for i in tuple_key_combination) #重複していなければ新しいのはopenable_key
                else:
                    now_price = key_price[openable_key]
                    
                keys_and_sum_price[tuple_key_combination] = now_price
            else:
                #print("重複")
                now_price = keys_and_sum_price[tuple_key_combination]
                
            #print(now_price,",",cheapest_price)    
            #既に高かったら、そこで枝刈り
            
            if now_price < cheapest_price:
                #全部の箱に対して鍵を選択済みか
                if box_number == N-1: #Yes→価格比較
                    #print("堀り終了")
                    #print("最安値更新:",now_price)
                    cheapest_price = now_price
                else: #No→再帰する
                    #print("深堀り")
                    cheapest_price = get_price_of_cheap_key_combination(box_number+1,cheapest_price,key_combination)
            #else:
                #print("枝刈り")
           
            #key_combination_pop(-1)
        
        return cheapest_price
        
    print(get_price_of_cheap_key_combination(0,cheapest_price,key_combination))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int, input().split())
    a = []
    c = []
    dp = [10 ** 7 for j in range(2 ** n)]
    dp[0] = 0
    for _ in range(m):
        a, b = map(int, input().split())
        sc = list(map(int, input().split()))
        c = 0
        for j in sc:
            c += 2 ** (j - 1)
        for j in range(2 ** n):
            dp[int(j | c)] = min(dp[int(j | c)], dp[j] + a)

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


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m = map(int, input().split())
    a = []
    c = []
    for i in range(m):
        sa, sb = map(int, input().split())
        sc = list(map(int, input().split()))
        tc = 0
        a.append(sa)
        for j in sc:
            tc += 2 ** (j - 1)
        c.append(tc)

    dp = [10 ** 7 for j in range(2 ** n)]
    dp[0] = 0
    for i in range(m):
        sc = c[i]
        for j in range(2 ** n):
            dp[int(j | sc)] = min(dp[int(j | sc)], dp[j] + a[i])

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


main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = []
c = []
for i in range(m):
    sa, sb = map(int, input().split())
    sc = list(map(int, input().split()))
    tc = 0
    a.append(sa)
    for j in sc:
        tc += 2 ** (j - 1)
    c.append(tc)

dp = [10 ** 7 for j in range(2 ** n)]
dp[0] = 0
for i in range(m):
    sc = c[i]
    for j in range(2 ** n):
        dp[int(j | sc)] = min(dp[int(j | sc)], dp[j] + a[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())
a = []
c = []
for i in range(m):
    sa, sb = map(int, input().split())
    sc = list(map(int, input().split()))
    tc = 0
    a.append(sa)
    for j in sc:
        tc += 2 ** (j - 1)
    c.append(tc)

dp = [10 ** 7 for j in range(2 ** n)]
for i in range(m + 1):
    dp[0] = 0
for i in range(m):
    sc = c[i]
    for j in range(2 ** n):
        dp[int(j | sc)] = min(dp[int(j | sc)], dp[j] + a[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())
vals = []
inf = float("inf")
ans = [inf]*2**n

for i in range(m):
	a,b = map(int,input().split())
	C = list(map(int,input().split()))
	cur = 0
	for c in C:
		cur += 2**(c-1)
	ans[cur] = min(ans[cur],a)

for i,a in enumerate(ans):
	if a == inf: continue
	for j,b in enumerate(ans):
		if b == inf: continue
		ans[i|j] = min(ans[i|j],ans[i]+ans[j])

if ans[-1] == inf:
	print(-1)
else:
	print(ans[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = map(int, input().split())
key_list = [[0,0]]*M
for _ in range(M):
    a, b = input().split()
    s = 0
    c_list = input().split()
    for i in c_list:
        s |= (1 << (int(i)-1))
    key_list.append([s, int(a)])

dp = [sys.maxsize]*((1 << N)) # N=3の時 111まで表したい 一見1<<2で良さげだがそうすると100までしかできない 111までにするには1<<3と1000の一個下までにする必要がある
dp[0] = 0
for i in range(1 << N):
    for key in key_list:
        s = (i | key[0])
        dp[s] = min([dp[s], dp[i] + key[1]])

if (dp[(1 << N)-1] == sys.maxsize):
    print("-1")
else:
    print(dp[(1 << N)-1])

Submission status: Time Limit Exceeded

Solution code:
import sys

N, M = map(int, input().split())
key_list = [[0,0]]*M
for _ in range(M):
    a, b = map(int, input().split())
    s = 0
    c_list = list(map(int, input().split()))
    for i in c_list:
        s |= (1 << (i-1))
    key_list.append([s, a])

dp = [sys.maxsize]*((1 << N)) # N=3の時 111まで表したい 一見1<<2で良さげだがそうすると100までしかできない 111までにするには1<<3と1000の一個下までにする必要がある
dp[0] = 0
for i in range(1 << N):
    for key in key_list:
        s = (i | key[0])
        dp[s] = min([dp[s], dp[i] + key[1]])

if (dp[(1 << N)-1] == sys.maxsize):
    print("-1")
else:
    print(dp[(1 << N)-1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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()))
    key = np.sum([2**(x-1) for x in c])
    
    ndp = dp.copy()
    for j in range(2**N):
        if dp[j | key] > ndp[j] + a:
            dp[j | key] = ndp[j] + a
            
if dp[-1] == float('inf'):
  print(-1)
else:
  print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations,permutations

n,m = map(int,input().split())
prices,keys = [],[]
for i in range(m):
	a,b = map(int,input().split())
	C = list(map(int,input().split()))

	prices.append(a)
	cur_key = 0
	for c in C:
		cur_key += 2**(c-1)
	keys.append(cur_key)
ans_max = 2**n-1
cnt = 0
ans = float("inf")
for i in range(1,m+1):
	for comb in combinations(range(0,m),r=i):
		# print(comb)
		price = 0
		cur_key = 0
		for c in comb:
			price += prices[c]
			cur_key |= keys[c]
		# print(price,cur_key)
		if cur_key == ans_max and price < ans:
			ans = price
if ans == float("inf"):
	ans = -1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
INF = 10**9
N, M = map(int, input().split())
dp = [INF for _ in range(2**N)]
dp[0] = 0
for i in range(M):
    a, _ = map(int, input().split())
    *C, = map(int, input().split())
    open_bit = 0
    for i in C: open_bit |= 1 << i-1
    for i in range(2**N): dp[i|open_bit] = min(dp[i|open_bit], dp[i] + a)
print(dp[-1] if dp[-1] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
INF = float('inf')
N, M = map(int, input().split())
dp = [INF for _ in range(2**N)]
dp[0] = 0
for i in range(M):
    a, _ = map(int, input().split())
    *C, = map(int, input().split())
    open_bit = 0
    for i in C: open_bit |= 1 << i-1
    for i in range(2**N): dp[i|open_bit] = min(dp[i|open_bit], dp[i] + a)
print(dp[-1] if dp[-1] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:

N, K = map(int, input().split())
key_data_list = []
for _ in range(K):
    value, op = map(int, input().split())
    open_boxes = map(int, input().split())
    box_value = 0
    for opb in open_boxes:
      box_value += 2**(opb-1)
    key_data_list.append([value, box_value])

import numpy as np

max_tresure_state = 2**N
max_key_price = 2**30
dp_table = np.full((K+1,max_tresure_state),max_key_price)

dp_table[0][0] = 0

for key_index in range(K):
    for tresure_state in range(max_tresure_state):
        key_value = key_data_list[key_index][0]
        key_state = key_data_list[key_index][1]

        if dp_table[key_index+1][tresure_state] > dp_table[key_index][tresure_state]:
            dp_table[key_index+1][tresure_state] = dp_table[key_index][tresure_state]

        buying_state = key_state | tresure_state
        dp_table[key_index+1][buying_state] = min(dp_table[key_index][buying_state],
                                                  dp_table[key_index+1][buying_state],
                                                  dp_table[key_index][tresure_state] + key_value)


result_value = dp_table[K][max_tresure_state-1]
if result_value == max_key_price:
    print(-1)
else:
    print(int(result_value))

Submission status: Time Limit Exceeded

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

N,M = map(int, input().split())
full = 2**N
dp = [float("inf")]*full
dp[0] = 0

for m in range(M):
    a,b = map(int, input().split())
    C = list(map(int, input().split()))
    num = 0
    for c in C:
        num += 2**(c-1)
    for i in range(full):
        if dp[i]!=float("inf"):
            dp[i|num] = min(dp[i|num],dp[i]+a)
print(dp[-1] if dp[-1]!=float("inf") else -1)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
V = []
INF = float("inf")
dp = [INF]*(1<<N)
dp[0] = 0
for i in range(M):
  a,b = map(int, input().split())
  c = list(map(int, input().split()))
  k = 0
  for j in range(b):
    k |= 1<<(c[j]-1)
  V.append((a,k))
  dp[k] = min(dp[k],a)

for i in range(1<<N):
  for a,k in V:
    dp[i|k] = min(dp[i|k],dp[i]+dp[k])  
print(dp[-1] if dp[-1] != INF else -1)

Submission status: Time Limit Exceeded

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

openable_box_and_price = {} #開けられる箱のtaple:値段 なdict

#同じ箱を開けられる鍵は最安値のものを選びつつ、読み込み
for i in range(M):
    a,b = map(int, input().split())
    c = tuple(map(int, input().split()))
    
    #print(c,":",a)
    
    if c in openable_box_and_price:
        #print("重複")
        if openable_box_and_price[c] > a:
            #print("安値更新")
            openable_box_and_price[c] = a
    else:
        openable_box_and_price[c] = a

#鍵に番号(0～)を付けるためlist化
key_price = list(openable_box_and_price.values())
key_openable_box = list(openable_box_and_price.keys())

#ある箱を開けられる鍵のリストを作る
key_number = 0
box_and_openable_key = [[] for _ in range(N)]

for openable_boxes in key_openable_box:
    for openable_box in openable_boxes:
        box_and_openable_key[openable_box-1].append(key_number)

    key_number += 1

#すべての箱を開けられる鍵の組み合わせのうち、最安値を求める。
no_ans_flag = 0

#そもそも開けられる鍵が無い箱があったら-1を出力
for openable_key in box_and_openable_key:
    if not openable_key:
        print(-1)
        no_ans_flag = 1
        break
        
if no_ans_flag != 1:
    def choice_keys(box_number):
        for key_number in box_and_openable_key[box_number]: #箱を開けられる鍵から1個選ぶ
            choiced_keys.append(key_number)
            if len(choiced_keys) != N: #すべての箱に対して鍵を選んでなかったら
                choice_keys(box_number+1) #さらに選ぶ
            else: #すべての箱に対して鍵を選んでたら
                #値段を計算する
                
                choiced_keys_set = set(choiced_keys) #重複選択している鍵を削除する

                if tuple(choiced_keys_set) not in caluclated_key_set_and_price: #setでは辞書のkeyに使えないので、tuple化
                    #値段計算
                    total_price = 0
                    for choiced_key in choiced_keys_set:
                        total_price += key_price[choiced_key]

                    caluclated_key_set_and_price[tuple(choiced_keys_set)] = total_price

                    #print(choiced_keys,":",choiced_keys_set,":",total_price)

                choiced_keys.pop(-1)

        if len(choiced_keys)!=0:
            choiced_keys.pop(-1)        

           
    caluclated_key_set_and_price = {}
    choiced_keys = []
    choice_keys(0)

    #求めたすべての箱を開けられる鍵の選択肢一覧から最安を選ぶ
    #print(caluclated_key_set_and_price)
    caluclated_key_set_and_price = sorted(caluclated_key_set_and_price.items(), key=lambda x:x[1])
    #print(caluclated_key_set_and_price)
    print(caluclated_key_set_and_price[0][1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    ABC = []
    c_all_or = 0
    where_open = lambda s: sum(2**j for j in s)
    for i in range(M):
        a, b = (int(j) for j in input().split())
        c = {int(j)-1 for j in input().split()}
        c_all_or |= where_open(c)
        ABC.append((a,b,c))
    if c_all_or != ((1<<N) - 1):
        print(-1)
        return 0
    r = [10**9] * (1<<N)
    r[0] = 0
    for bit in range(1,1<<N):
        q = r[bit]
        for i in range(M):
            cur = where_open(ABC[i][2])
            less = (bit ^ cur) & bit
            q = min(q,r[less] + ABC[i][0])
        r[bit] = q
    
    print(r[(1<<N) - 1])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    ABC = []
    c_all_or = 0
    for i in range(M):
        a, b = (int(j) for j in input().split())
        c = {int(j)-1 for j in input().split()}
        c_all_or |= sum(2**j for j in c)
        ABC.append((a,b,c))
    if c_all_or != ((1<<N) - 1):
        print(-1)
        return 0
    r = [10**9] * (1<<N)
    r[0] = 0
    for bit in range(1,1<<N):
        q = r[bit]
        for i in range(M):
            cur = sum(2**j for j in ABC[i][2])
            less = (bit ^ cur) & bit
            q = min(q,r[less] + ABC[i][0])
        r[bit] = q
    
    print(r[(1<<N) - 1])
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

can=[]
costs=[]
kind=[]#0~4095
kind_sets=[]
def hash_l(l):
  ans=0
  for num in l:
    ans=ans+2**(num-1)
  return ans
def int2list(n):
    res = list()
    elm = 0
    while n != 0:
        if (n ^ 1 << elm) < n:
            res.append(elm+1)
            n ^= 1 << elm
        elm += 1
    return set(res)
for i in range(M):
  a,_=map(int,input().split())
  costs.append(a)
  s=set(map(int,input().split()))
  kind.append(s)
for i in range(2**N):
  kind_sets.append(int2list(i))
dp=[[float('inf')]*(2**N) for i in range(M)]# M*kind=cost


for j in range(2**N):
  if kind[0]>=kind_sets[j]:
    dp[0][j]=costs[0]
dp[0][0]=0
for i in range(1,M):
  cost=costs[i]
  for j in range(2**N):
    if kind[i].isdisjoint(kind_sets[j]):
      dp[i][j]=dp[i-1][j]
    else:
      min_cost=float('inf')
      aim=kind_sets[j]- kind[i]
      for k in range(2**N):
        if aim<=kind_sets[k]:
          min_cost=min(min_cost,dp[i-1][k]+cost)
      dp[i][j]=min(dp[i-1][j],min_cost)
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:
from sys import setrecursionlimit

def read_key():
    a, _ = map(int, input().split())
    m = 0
    for c in map(int, input().split()):
        m |= 1 << (c - 1)
    return (a, m)

def solve(keys, amount, cm, dp):
  if cm == (1 << N) - 1:
    return amount
  if len(keys) == 0:
    return INF
  a, m = keys[0]
  if dp[cm | m] < amount + a:
    return solve(keys[1:], amount, cm, dp)
  else:
    dp[cm | m] = amount + a
    return min(solve(keys[1:], amount + a, cm | m, dp), solve(keys[1:], amount, cm, dp))

setrecursionlimit(1000000)
INF = float('inf')

N, M = map(int, input().split())
keys = [read_key() for _ in range(M)]

dp = [INF] * (1 << N)
t = solve(keys, 0, 0, dp)
if t == INF:
  print(-1)
else:
  print(t)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit

def read_key():
    a, _ = map(int, input().split())
    m = 0
    for c in map(int, input().split()):
        m |= 1 << (c - 1)
    return (a, m)

def solve(keys, amount, cm, dp):
  if cm == (1 << N) - 1:
    return amount
  if len(keys) == 0:
    return INF
  a, m = keys[0]
  if dp[cm | m] < amount + a:
    return solve(keys[1:], amount, cm, dp)
  else:
    dp[cm | m] = amount + a
    return min(solve(keys[1:], amount, cm, dp), solve(keys[1:], amount + a, cm | m, dp))

setrecursionlimit(1000000)
INF = float('inf')

N, M = map(int, input().split())
keys = [read_key() for _ in range(M)]

dp = [INF] * (1 << N)
t = solve(keys, 0, 0, dp)
if t == INF:
  print(-1)
else:
  print(t)

Submission status: Time Limit Exceeded

Solution code:
def read_key():
    a, _ = map(int, input().split())
    m = 0
    for c in map(int, input().split()):
        m |= 1 << (c - 1)
    return (a, m)

from sys import setrecursionlimit
setrecursionlimit(1000000)
INF = float('inf')

N, M = map(int, input().split())
keys = [read_key() for _ in range(M)]

dp = [INF] * (1 << N)
def solve(keys, amount, cm):
  if cm == (1 << N) - 1:
    return amount
  if len(keys) == 0:
    return INF
  a, m = keys[0]
  if dp[cm | m] < amount + a:
    return solve(keys[1:], amount, cm)
  else:
    dp[cm | m] = amount + a
    return min(solve(keys[1:], amount, cm), solve(keys[1:], amount + a, cm | m))

t = solve(keys, 0, 0)
if t == INF:
  print(-1)
else:
  print(t)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
l = []
wa = 0
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    wa += a
    l.append([a,b,c])
dp = [[wa + 1 for i in range(2**n)] for i in range(m+1)]
bit = 2**n
#print(l)
for i in range(1,m+1):
    a,b,c = l[i-1]
    bitc = 0
    for x in c:
        bitc += 2**(x-1)
    for j in range(bit):
        j2 = j
        mod = 1
        for k in range(n):
            if (j >> k) & 1:
                continue
            else:
                if (bitc >> k) & 1:
                    j2 += 2**k
        #print(i,j,j2)
        if j == 0:
            dp[i][j2] = min([dp[i-1][j2],a,dp[i][j2]])
        else:
            dp[i][j2] = min([dp[i-1][j]+a,dp[i-1][j2],dp[i][j2]])
        if j2 != j:
            dp[i][j] = dp[i-1][j]
ans = dp[m][bit-1]
#print(dp)
if ans <= wa:
    print(dp[m][bit-1])
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
#input
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())
    C[i] = list(map(int, input().split()))

#output
dp = [9**9]* (1<<N)

def list_to_bin(my_list):
    my_bin = 0
    for l in my_list:
        my_bin += 1<<(l-1)
    return my_bin

dp[0] = 0
for i in range(M):
    for s in range(1<<N):
        dp[s|list_to_bin(C[i])] = min(dp[s|list_to_bin(C[i])], dp[s] + A[i])

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

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
a=[0 for i in range(m)]
b=[0 for i in range(m)]
c=[[] for i in range(m)]
for i in range(m):
  a[i],b[i]=map(int,input().split())
  c[i]=list(map(int,input().split()))
  
dp=[float("inf") for i in range(2**n)]
dp[0]=0
for i in range(m):
  now=0
  for j in c[i]:
    jj=1<<j-1
    now=now|jj
  for k in range(2**n):
    kk=k|now
    dp[kk]=min(dp[kk],dp[k]+a[i])
    

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

Submission status: Time Limit Exceeded

Solution code:
n,m  = list(map(int, input().split()))
ab =[]
cs =[]
for i in range(m):
    ab.append(list(map(int, input().split())))
    cs.append(list(map(int, input().split())))

dp = [float("inf") for _ in range(1 << n)]
dp[0] = 0

for i in range(m):
    csbit = 0
    for j in cs[i]:
        csbit += 2**(j-1)
    for j in range(1 << n):
        dp[j | csbit] = min(dp[j | csbit], dp[j] + ab[i][0])

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

Submission status: Time Limit Exceeded

Solution code:

n,m  = list(map(int, input().split()))
ab =[]
cs =[]
for i in range(m):
    ab.append(list(map(int, input().split())))
    cs.append(list(map(int, input().split())))

csbit = []
for i in cs:
    csum = 0
    for j in i:
        csum += 2**(j-1)
    csbit.append(csum)

dp = [float("inf") for _ in range(1 << n)]
dp[0] = 0

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

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