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 numpy as np

n, m = map(int, input().strip().split())
dp = [float('inf')] * (1 << n)
dp[0] = 0
for i in range(m):
    a, b = map(int, input().strip().split())
    c = np.array(list(map(int, input().strip().split()))) - 1
    mask = 0b0
    for i in c:
        mask |= 0b1 << i

    for j in range(1 << n):
        if dp[j] < float('inf'):
            dp[j | mask] = min(dp[j] + a, dp[j | mask])

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())
t=[]
for i in range(m):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    d=0
    for i in c:
        d+=2**(i-1)
    t.append([a,d])
e=[float("INF")]*(2**n)
e[0]=0
for i,j in t:
    for h in range(2**n):
        e[h|j]=min(i+e[h],e[h|j])
print(e[-1] if e[-1]!=float("INF") else -1)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
N,M=map(int,input().split())
l=list(product((0,1),repeat=N))
L=len(l)
for i in range(2**N):
    l[i]=[l[i],1300000]
r=(2048,1024,512,256,128,64,32,16,8,4,2,1)
l[0][1]=0
for i in range(M):
    a,b=map(int,input().split())
    c=tuple(map(int,input().split()))
    t=[0]*N
    for j in c:
        t[-j]=1
    for j in range(L):
        s=0
        for k in range(N):
            if l[j][0][-k-1] or t[-k-1]:
                s+=r[-k-1]
        l[s][1]=min(l[j][1]+a,l[s][1])
if l[-1][1]==1300000:
    print(-1)
else:
    print(l[-1][1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)

def binize(vn):
    res = 0
    for n in vn:
        res |= 1 << (n-1)
    return res


N, M = map(int, input().split())
mK = []
for i in range(M):
    a, b = map(int, input().split())
    vc = list(map(int, input().split()))
    mK.append((a, binize(vc)))

allOpen = 2**N - 1

dA = dict()
dA[0] = [0,]
qA = [0,]

for a, c in mK:
    for aPre in qA:
        for x in dA[aPre]:
            if (x | c) in dA[aPre]:
                continue
            else:
                if (aPre + a) in qA:
                    if allOpen in dA[aPre + a]:
                        continue
                    else:
                        dA[aPre + a].append(x | c) 
                else:
                    dA[aPre + a] = [(x | c),]
                    qA.append(aPre + a)

#print(dA)
#print(max(dA.values()))
#print(allOpen)

res = 10 ** 30
for k in dA:
    if allOpen in dA[k]:
        res = min(res, k)

#print(res)
print(res if res != 10**30 else -1)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
from itertools import combinations
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

def subsets(items):
    _subsets_=[]
    for i in range(len(items) + 1):
        for c in combinations(items, i):
            _subsets_.append(c)
    return _subsets_

INF = 999999999999999999999999

n,m = get_nums_l()

# ある扉の組み合わせを鍵1本で開けられる最小コストのリスト
keys = [INF] * (2 ** (n+2))

for _ in range(m):
    cost, b = get_nums_l()
    ccc = get_nums_l()

    # print(cost,b)


    for s in subsets(ccc):
        keyn = 0
        # print(s)
        for c in s:
            keyn += 2 ** c
        
        #print("keyn", keyn)
        if keys[keyn] > cost:
            keys[keyn] = cost

# print(keys)

# そもそも開けられない扉があったら無理
for i in range(1,n+1):
    if keys[2**i] == INF:
        print(-1)
        exit()

memo=[None] * (2 ** (n+2))

def solve(targets):

    lent = len(targets)
    
    # print(targets)

    if lent == 0:
        return 0

    if lent == 1:
        memo[2*list(targets)[0]] = keys[2*list(targets)[0]]
        # print(targets, keys[2**list(targets)[0]])
        return keys[2**list(targets)[0]]

    all_s = set(targets)

    keyn=0
    for c in targets:
        keyn += 2 ** c
    
    if memo[keyn]:
        return memo[keyn]

    _min = keys[keyn]

    for s in subsets(targets):
        if len(s) in (0, lent):
            continue
        rev = all_s.difference(s)
        cost = solve(s) + solve(rev)
        if _min > cost:
            _min = cost
    memo[keyn] = _min
    # print(targets, memo[keyn])
    return _min


ans = solve(set(range(1, n+1)))
# print(memo)
print(ans if ans < INF else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys, copy
from collections import deque


input = sys.stdin.readline
N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
prices = [-1]*M
C = []
for i in range(M):
  A,B = map(int,input().split())
  prices[i] = A
  tmpC = [1]*12
  for c in map(int,input().split()):
    tmpC[c-1] = 0
    graph[c-1].append(i)
  C.append(tmpC)

queue = deque()
queue.append([[1]*N,0])
ans = (10**5)*M + 1
while len(queue) != 0:
  prv_boxes, prv_prc = queue.pop()
  if 1 not in prv_boxes:
    ans=min(ans,prv_prc)
    continue
  if prv_prc >= ans: continue
  prv_box_i = prv_boxes.index(1)
  for key_i in graph[prv_box_i]:
    queue.append([[i*j for i,j in zip(prv_boxes, C[key_i])], prv_prc+prices[key_i]])
print(-1 if ans == (10**5)*M + 1 else ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
INF = 10 ** 12
dp = [INF] * (2**N)
dp[0] = 0
for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    base = sum(2**(c-1) for c in C)
    for j in range(2**N):
        if any(not ((j >> (c-1)) & 1) for c in C):
            step = base - sum(2**(c-1) for c in C if ((j >> (c-1)) & 1))
            dp[j+step] = min(dp[j+step], dp[j]+a)

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

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
from itertools import combinations
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

def subsets(items):
    _subsets_=[]
    for i in range(len(items) + 1):
        for c in combinations(items, i):
            _subsets_.append(c)
    return _subsets_

INF = 999999999999999999999999

n,m = get_nums_l()

# ある扉の組み合わせを鍵1本で開けられる最小コストのリスト
keys = [INF] * (2 ** (n+2))

for _ in range(m):
    cost, b = get_nums_l()
    ccc = get_nums_l()

    # print(cost,b)


    for s in subsets(ccc):
        keyn = 0
        # print(s)
        for c in s:
            keyn += 2 ** c
        
        #print("keyn", keyn)
        if keys[keyn] > cost:
            keys[keyn] = cost

# print(keys)

# そもそも開けられない扉があったら無理
for i in range(1,n+1):
    if keys[2**i] == INF:
        print(-1)
        exit()

memo=[None] * (2 ** (n+2))

def solve(targets):
    
    # print(targets)

    if len(targets) == 0:
        return 0

    if len(targets) == 1:
        # memo[2*list(targets)[0]] = keys[2*list(targets)[0]]
        # print(targets, keys[2**list(targets)[0]])
        return keys[2**list(targets)[0]]

    all_s = set(targets)

    keyn=0
    for c in targets:
        keyn += 2 ** c
    
    if memo[keyn]:
        return memo[keyn]

    _min = keys[keyn]

    for s in subsets(targets):
        if len(s) == 0 or len(s) == len(targets):
            continue
        rev = all_s.difference(s)
        cost = solve(s) + solve(rev)
        if _min > cost:
            _min = cost
    memo[keyn] = _min
    # print(targets, memo[keyn])
    return _min


ans = solve(set(range(1, n+1)))
# print(memo)
print(ans if ans < INF else -1)

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[i],_=map(int,input().split())
    c[i]=sum(map(lambda x:2**(int(x)-1),input().split()))
dp=[INF]*(2**n)
dp[0]=0
for i in range(m):
    for j in range(2**n):
        dp[c[i]|j]=min(dp[c[i]|j],dp[j]+a[i])
print(-1 if dp[-1]==INF else dp[-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import product
input = sys.stdin.readline
N, M = map(int, input().split())
INF = 10 ** 12
dp = [INF] * (2**N)
dp[0] = 0
for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    base = sum(2**(c-1) for c in C)
    for j in range(2**N):
        if any(not ((j >> (c-1)) & 1) for c in C):
            step = base - sum(2**(c-1) for c in C if ((j >> (c-1)) & 1))
            dp[j+step] = min(dp[j+step], dp[j]+a)

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

Submission status: Time Limit Exceeded

Solution code:
import sys, copy
from collections import deque


input = sys.stdin.readline
N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
prices = [-1]*M
C = []
for i in range(M):
  A,B = map(int,input().split())
  prices[i] = A
  tmpC = [1]*12
  for c in map(int,input().split()):
    tmpC[c-1] = 0
    graph[c-1].append(i)
  C.append(tmpC)

queue = deque()
queue.append([[1]*N,0])
ans = float('inf')
flag = False
while len(queue) != 0:
  prv_boxes, prv_prc = queue.pop()
  if 1 not in prv_boxes:
    ans=min(ans,prv_prc)
    flag = True
    continue
  if prv_prc >= ans: continue
  prv_box_i = prv_boxes.index(1)
  for key_i in graph[prv_box_i]:
    queue.append([[i*j for i,j in zip(prv_boxes, C[key_i])], prv_prc+prices[key_i]])
print(-1 if flag is False else ans)

Submission status: Time Limit Exceeded

Solution code:
input = raw_input

N,M = map(int, input().split(" "))

kp = []
ko = []

for i in range(M):
    a,b = map(int, input().split(" "))
    kp.append(a)
    ko.append(list(map(int, input().split(" "))))


mo = [1] * N
for i in range(M):
    for j in ko[i]:
        mo[j-1] = 0
if sum(mo) > 0:
    print(-1)
    exit()

def op(x):
    no = [1] * N
    for i in range(M):
        if x[i] == 1:
            for j in ko[i]:
                no[j-1] = 0
    if sum(no) > 0:
        return False
    return True

def pr(x):
    c = 0
    for i in range(M):
        if x[i] == 1:
            c += kp[i]
    return c

l = [[1] * M]
mlst = []

while True:
    l2 = []
    for x in l:
        end = True
        for i in range(M):
            ltmp = x[:]
            if ltmp[i] == 1:
                ltmp[i] = 0
                if op(ltmp):
                    end = False
                    if not ltmp in l2:
                        l2.append(ltmp)
        if end:
            mlst.append(x[:]+[pr(x)])
    if l2 == []:
        break
    else:
        l = l2
mlst.sort(key = lambda x: x[M])
print(mlst[0][M])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from itertools import chain, combinations


def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))


def main():
    # N = int(input())
    # N,= [int(a) for a in input().split()]
    N, M = [int(a) for a in input().split()]

    A = []
    c = []

    for _ in range(M):
        aa, bb = [int(a) for a in input().split()]
        cc = [int(a) for a in input().split()]
        A.append(aa)
        c.append(cc)

    aa = set()
    for cc in c:
        aa |= set(cc)
    if len(aa) != N:
        print(-1)
        return

    def f(takaras):
        res = 10 ** 6
        for i in range(M):
            if set(takaras).issubset(set(c[i])):
                res = min(res, A[i])
        if len(takaras) != 1:
            for a in powerset(takaras):
                if len(a) == len(takaras):
                    continue
                if len(a) == 0:
                    continue
                ho = takaras - set(a)
                r = f(set(a)) + f(ho)
                res = min(res, r)

        return res

    res = f(set(range(1, N + 1)))
    if res == 10 ** 6:
        print(-1)
    else:
        print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, copy
from collections import deque


input = sys.stdin.readline
N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
prices = [-1]*M
C = []
for i in range(M):
  A,B = map(int,input().split())
  prices[i] = A
  tmpC = [1]*12
  for c in map(int,input().split()):
    tmpC[c-1] = 0
    graph[c-1].append(i)
  C.append(tmpC)

queue = deque()
queue.append([[1]*N,0])
ans = float('inf')
flag = False
while len(queue) != 0:
  prv_boxes, prv_prc = queue.pop()
  if sum(prv_boxes) == 0:
    ans=min(ans,prv_prc)
    flag = True
    continue
  if prv_prc >= ans: continue
  prv_box_i = prv_boxes.index(1)
  for key_i in graph[prv_box_i]:
    queue.append([[i*j for i,j in zip(prv_boxes, C[key_i])], prv_prc+prices[key_i]])
print(-1 if flag is False else ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
N, M = map(int, input().split())
boxkey = [[[], 0] for _ in range(N)]
keymoney = [0 for _ in range(M)]

for i in range(M):
	a, b = list(map(int, input().split()))
	keymoney[i] = a
	C = list(map(int, input().split()))
	for c in C:
		boxkey[c - 1][0].append(i + 1)
		
for i in range(N):
	boxkey[i][1] = len(boxkey[i][0])

boxkey = sorted(boxkey, key = lambda x : (x[1]))
mini = float('inf')

	
minimum = float('inf')
end = 0

def dfs(blg_key, depth, money):
	global mini
	depth += 1
	if depth == N:
		mini = min(money, mini)
		return money
	else:
		# print(boxkey[depth][0])
		for i in boxkey[depth][0]:
			
			# print(i)
			t = copy.deepcopy(blg_key)
			if not i in blg_key:
				t.append(i)
				# print(t)
				dfs(t, depth, money + keymoney[i - 1])
			else:
				# print(t)
				dfs(t, depth, money)
				
				
for i in boxkey:
	if i[1] == 0:
		end = 1
		print(-1)
		break
if end == 0:
	for i in boxkey[0][0]:
		dfs([i], 0, keymoney[i - 1])
	print(mini)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
a_list = []
b_list = []
c_list = []
for _ in range(M):
    a, b = map(int,input().split())
    c = list(map(int,input().split()))
    c = [cc-1 for cc in c]
    a_list.append(a)
    b_list.append(b)
    c_list.append(c)


takara_keys = {}
for i in range(N):
    takara = []
    for idx, c in enumerate(c_list):
        if i in c:
            takara.append(idx)
    takara_keys[i] = takara

clear = [1 for _ in range(N)]
def dp(memos, cost):
    if memos == clear:
        return cost
    costs = [10**9]
    for takara, memo in enumerate(memos):
        hoge_flg = 0
        if memo == 0:
            hoge_flg = 1
            next_keys = takara_keys[takara]
            for key in next_keys:
                tmp_memos = memos[:]
                for takara_idx in c_list[key]:
                    tmp_memos[takara_idx] = 1
                tmp_cost = cost + a_list[key]
                costs.append(dp(tmp_memos,tmp_cost))
        if hoge_flg == 1:
            break
    return min(costs)

length_0_flag = False
for v in takara_keys.values():
    if len(v)==0:
        length_0_flag = True

if length_0_flag:
    print(-1)
else:
    print(dp([0 for _ in range(N)],0))

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
N, M = map(int, input().split())
INF = 10 ** 12
dp = [INF] * (2**N)
pp = [INF] * (2**N)
dp[0] = 0
for i in range(M):
    # dp[i]
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    base = sum(2**(c-1) for c in C)
    for j in range(2**N):
        if any(not ((j >> (c-1)) & 1) for c in C):
            step = base - sum(2**(c-1) for c in C if ((j >> (c-1)) & 1))
            dp[j+step] = min(dp[j+step], dp[j]+a)

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

Submission status: Time Limit Exceeded

Solution code:
import math
import random
import datetime

input = raw_input

N,M = map(int, input().split(" "))

kp = []
ko = []

for i in range(M):
    a,b = map(int, input().split(" "))
    kp.append(a)
    ko.append(list(map(int, input().split(" "))))


mo = [1] * N
for i in range(M):
    for j in ko[i]:
        mo[j-1] = 0
if sum(mo) > 0:
    print(-1)
    exit()

def op(x):
    no = [1] * N
    for i in range(M):
        if x[i] == 1:
            for j in ko[i]:
                no[j-1] = 0
    if sum(no) > 0:
        return False
    return True

def pr(x):
    c = 0
    for i in range(M):
        if x[i] == 1:
            c += kp[i]
    return c

l = [[1] * M]
mlst = []

while True:
    l2 = []
    for x in l:
        end = True
        for i in range(M):
            ltmp = x[:]
            if ltmp[i] == 1:
                ltmp[i] = 0
                if op(ltmp):
                    end = False
                    l2.append(ltmp)
        if end:
            mlst.append(x[:]+[pr(x)])
    if l2 == []:
        break
    else:
        l = l2
mlst.sort(key = lambda x: x[M])
print(mlst[0][M])

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import dijkstra

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

M = [[float("inf")] * 2**n for i in range(2**n)]

for i in range(2**n):
    M[i][i] = 0

for i in range(m):
    t = 0
    for j in C[i]:
        t += 2**(j-1)
    for j in range(2**n):
        for k in range(2**n):
            if (t-(k-j)) ^ (k-j) == t:
                # print(t,j)
                M[j][k] = min(M[j][k], A[i][0])
# print(M)

d = dijkstra(M, indices = 0)

ans = d[-1]
if ans == float("inf"):
    ans = -1
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:

# 1 2
n, m = list(map(int, input().split()))
c = [None]*m

key_prices = [0]*m
key_targets = [None]*m

for i in range(m):
    yen, matches_num = list(map(int, input().split()))
    key_prices[i] = yen
    key_targets[i] = set(map(int, input().split()))


min_price = -1


def calc(i, status):
    res = 0

    if i >= m:
        # res = 0
        if len(status) >= n:
            # print(status)
            # print(res)
            global min_price
            if res != 0 and (min_price == -1 or min_price > res):
                min_price = res
        else:
            res = 999999999
    elif key_targets[i] < status:
        # 入れる意味がない
        res = calc(i+1, status)
    else:
        r1 = calc(i+1, status)
        status = status | key_targets[i]
        r2 = calc(i+1, status)+key_prices[i]
        res = min(r1, r2)
    # memo[memo_key] = res

    return res


r = calc(0, set())

if r == 999999999:
    print(-1)
else:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = []
b = []
c = []
for i in range(m):
    aa,bb = map(int,input().split())
    a.append(aa)
    b.append(bb)
    cc = list(map(int,input().split()))
    c.append(cc)

inf = 888888888888888888
maaa = 2 ** 12
nedan = [inf] * maaa 
nedan[0] = 0

def to_bit(ima):
    now = 0
    for i in range(n):
        if ima[i] == 1:
            now += 2**i
    return now 

def check(ima,bbb):
    ima2 = [0]*n
    for i in range(n):
      ima2[i] = ima[i]
    flag = False
    for i in range(b[bbb]):
        if ima[c[bbb][i]-1] == 1:
            flag = True
            ima2[c[bbb][i] -1] = 0
    if flag:
        return ima2
    else:
        return -1
    
def dfs(ima):
    bii = to_bit(ima)
    if nedan[bii] != inf:
        return nedan[bii]
    now = inf
    for i in range(m):
        ima2 = check(ima,i)

        if ima2 == -1:
            continue
        else:
            cost = a[i] + dfs(ima2)
        now = min(cost,now)
    nedan[bii] = now
    return now

ima = [1]*n
kow = dfs(ima)
if kow == inf:
    print(-1)
else:
    print(kow)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import copy

class Key():
    def __init__(self, cost, open_set):
        self.cost = cost
        self.openable_set = open_set

    def openable(self, c):
        return c in self.openable_set


class KeySet():
    def __init__(self, first_key):
        self.keys = [first_key]
        self.total_cost = first_key.cost
        self.opened = set(first_key.openable_set)

    def add_key(self, key):
        self.keys.append(key)
        self.total_cost += key.cost
        self.opened |= key.openable_set


n, m = map(int, input().split())
cost = 0
keys = []
for _ in range(m):
    a, b = map(int, input().split())
    c = set(map(lambda x: int(x)-1, input().split()))
    keys.append(Key(a, c))

cand = [KeySet(k) for k in keys if k.openable(0)]
for i in range(1, n):
    new_cand = []
    needs_key = []

    for ks in cand:
        if i in ks.opened:
            new_cand.append(ks)
        else:
            needs_key.append(ks)

    open_i_cand = [k for k in keys if k.openable(i)]
    for add_key in open_i_cand:
        for nk in needs_key:
            nks = copy.deepcopy(nk)
            nks.add_key(add_key)
            new_cand.append(nks)

    cand = new_cand
    if len(cand) == 0:
        break


if len(cand) == 0:
    print(-1)
else:
    tc = cand[0].total_cost
    for ks in cand[1:]:
        tc = min(tc, ks.total_cost)
    print(tc)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
price = []
kagi = []
for i in range(M):
  price.append(int(input().split()[0]))
  key = 0
  kagikagi = list(map(int,input().split()))
  for k in kagikagi:
    key += 2 ** (k-1)
  kagi.append(key)

res = -1
for i in range(2**M):
  combi = 0
  tmp_res = 0
  keys = []
  for j in range(M):
    if((i >> j) & 1):
      combi = combi|kagi[j]
      tmp_res += price[j]
      keys.append(j)
  if combi == 2**N-1:
    if tmp_res < res or res == -1:
      res = tmp_res
      
print(res)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, M = list(int(el) for el in input().split(' '))

dicts={}
for i in range(M):
  ai, bi = list(int(el) for el in input().split(' '))
  i_key=set()
  for key in list(int(el) for el in input().split(' ')):
    i_key.add(key)
  
  dicts[i] = [ai, i_key]

minval = 10**16  
base_set=set()

for l in range(N):
  base_set.add(l+1)
  
is_imp = False
for k in range(M): 
 
  if is_imp:
    break
  
  for idxes in list(itertools.combinations(dicts, r=M-k)):
    
    now_set = set()
    total_val = 0
    for idx in idxes:
      now_set = now_set | dicts[idx][1]
      total_val += dicts[idx][0]
  
    if now_set==base_set:
      if total_val < minval:
        minval = total_val
    else:
      if k==0: 
        is_imp=True
        break

if not is_imp:
  print(minval)
else:
  print(-1)

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[i],_=map(int,input().split())
    c[i]=sum(map(lambda x:2**(int(x)-1),input().split()))
dp=[INF]*(2**n)
for i in range(m):
    for j in range(2**n):
        if j|c[i]==c[i]:
            dp[j]=min(dp[j],a[i])
        dp[c[i]|j]=min(dp[c[i]|j],dp[j]+a[i])
print(-1 if dp[-1]==INF else dp[-1])

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
a,b,c,d,min=[],[],[],[0]*M,1e12
for i in range(M):
  aa,bb=map(int,input().split())
  a+=[aa];b+=[bb]
  c+=[list(map(int,input().split()))]

#aa,bb,cc=zip(*sorted(zip(a,b,c)))
for i in range(M):
  d[i]=0
  for j in range(len(c[i])):
    d[i]+=1<<(c[i][j]-1)
#print(d)

for i in range(2**M):
  aaa,ddd=0,0
  for j in range(M):
    if ((2<<j) & i) != 0:
      aaa+=a[j]
      ddd|=d[j]
#  print(i,j,aaa,ddd)
  if ddd==2**N-1:
    if min>aaa:min=aaa
if min>1e11:min=-1
print(min)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ab = []
c = []
check = list(i for i in range(1, N+1))
for _ in range(M):
    ab.append(list(map(int, input().split())))
    c.append(list(map(int, input().split())))

open_list = []
min_cost = 10**9
for i in range((2**M)-1):
    tmp = 0
    open_list = []
    for m in range(M):
        if (i >> m) & 1:
            open_list += c[m]
            tmp += ab[m][0]
    if check == list(set(open_list)):
        #print(check, list(set(open_list)))
        #print(min_cost, tmp)
        min_cost = min(tmp, min_cost)

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,M=map(int,input().split())
a,b,c,d,min=[],[],[],[0]*M,1e12
for i in range(M):
  aa,bb=map(int,input().split())
  a+=[aa];b+=[bb]
  c+=[list(map(int,input().split()))]

#aa,bb,cc=zip(*sorted(zip(a,b,c)))
for i in range(M):
  d[i]=0
  for j in range(len(c[i])):
    d[i]+=1<<(c[i][j]-1)
#print(d)

for i in range(2**M):
  aaa,ddd=0,0
  for j in range(M):
    if ((2<<j) & i) != 0:
      aaa+=a[j]
      ddd|=d[j]
#  print(i,j,aaa,ddd)
  if ddd==2**N-1:
    if min>aaa:min=aaa
if min>1e11:min=-1
print(min)

Submission status: Time Limit Exceeded

Solution code:
# TLE
import sys
sys.setrecursionlimit(100000)


def like_napsac(ite, price, box_set):
    if ite == M:
        if len(box_set) != N:
            return 10 ** 9
        else:
            return price
    elif len(box_set) == N:
        return price
    elif box_set | key_box[ite] == box_set:
        return like_napsac(ite + 1, price, box_set)

    else:
        return min(like_napsac(ite + 1, price, box_set), like_napsac(ite+1, price+key[ite][0], box_set | key_box[ite]))


N, M = map(int, input().split())
key = [0] * M
key_box = [0]*M
for i in range(M):
    key[i] = [0] * 2
    key[i][0], key[i][1] = map(int, input().split())
    key_box[i] = set([int(x) for x in input().split()])
ans = like_napsac(0, 0, set())
if ans == 10 ** 9:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
a_list = []
b_list = []
c_list = []
for _ in range(M):
    a, b = map(int,input().split())
    c = list(map(int,input().split()))
    c = [cc-1 for cc in c]
    a_list.append(a)
    b_list.append(b)
    c_list.append(c)


takara_keys = {}
for i in range(N):
    takara = []
    for idx, c in enumerate(c_list):
        if i in c:
            takara.append(idx)
    takara_keys[i] = takara

clear = [1 for _ in range(N)]
def dp(memos, cost):
    if memos == clear:
        return cost
    costs = [10**9]
    for takara, memo in enumerate(memos):
        if memo == 0:
            next_keys = takara_keys[takara]
            for key in next_keys:
                tmp_memos = memos[:]
                for takara_idx in c_list[key]:
                    tmp_memos[takara_idx] = 1
                tmp_cost = cost + a_list[key]
                costs.append(dp(tmp_memos,tmp_cost))
    return min(costs)

length_0_flag = False
for v in takara_keys.values():
    if len(v)==0:
        length_0_flag = True

if length_0_flag:
    print(-1)
else:
    print(dp([0 for _ in range(N)],0))

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,M=map(int,input().split())
a,b,c,d,min=[],[],[],[0]*M,1e12
for i in range(M):
  aa,bb=map(int,input().split())
  a+=[aa];b+=[bb]
  c+=[list(map(int,input().split()))]

aa,bb,cc=zip(*sorted(zip(a,b,c)))
for i in range(M):
  d[i]=0
  for j in range(len(c[i])):
    d[i]+=1<<(c[i][j]-1)
#print(d)

for i in range(2**M):
  aaa,ddd=0,0
  for j in range(M):
    if ((2<<j) & i) != 0:
      aaa+=a[j]
      ddd|=d[j]
#  print(i,j,aaa,ddd)
  if ddd==2**N-1:
    if min>aaa:min=aaa
if min>1e11:min=-1
print(min)

Submission status: Time Limit Exceeded

Solution code:
def main():
    I=lambda:list(map(int,input().split()))
    n,m=I()
    e=eval('(I()[0],I()),'*m)
    I=9**9
    dp=[I]*2**n
    dp[0]=0
    for i,dpi in enumerate(dp):
        if dpi==I:continue
        for a,c in e:
            b=i
            for j in c:b|=2**(n-j)
            cost=dpi+a
            if dp[b]>cost:dp[b]=cost
    print(-(dp[-1]==I)or dp[-1])
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque
from heapq import *
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()

t = set([v for v in range(1, N + 1)])
L = [None] * M
for i in range(M):
    A, B, = map(int, input().split())
    C = [int(v) for v in input().split()]
    
    L[i] = (A, C)
    t = t - set(C)

if len(t) > 0:
    print(-1)
    exit()

ans = 10 ** 18
for i in range(1, 1 << M):
    t = set()

    for j in range(M):
        if (i >> j) & 1:
            t.add(j)

    m = set([v for v in range(1, N + 1)])
    score = 0
    for p in t:
        a = L[p]
        score += a[0]
        m = m - set(a[1])

    if len(m) == 0:
        ans = min(ans, score)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ab = [0]*M
C = [0]*M
for i in range(M):
    ab[i] = list(map(int, input().split()))
    C[i] = set(map(int, input().split()))

treasure = set(range(1, N+1))
MAX = 1000000
cost_ans = MAX
for i in range(2**M):
    cost = 0
    set_treasure = set()
    for j in range(M):
        if ((i>>j) & 1):
            cost += ab[j][0]
            set_treasure = set_treasure.union(C[j])
    if set_treasure == treasure:
        cost_ans = min(cost_ans, cost)
           
if cost_ans == MAX:
    print(-1)
else:
    print(cost_ans)