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
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(n, opened, res):
  global ans
  for i in range(1, N+1):
    if str(i) not in opened:
      for x in data[i]:
        tami(x, 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
for i in range(1, N+1):
  tami(i, "", 0)
if ans == MAX_INT:
  print(-1)
else:
  print(ans)

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

if dp[-1] != INF:
    print(dp[-1])
else:
    print(-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, b = 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] + a, dp[i | c])

if dp[-1] != INF:
    print(dp[-1])
else:
    print(-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)]
dp[0][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][key_used_situation], 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:
n,m=map(int, input().split()) 
key=[]
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    rock = 0
    for j in c:
        rock += 2**(j-1)
    key.append([a,rock])

DP=[[float('inf')]*2**n for i in range(m+1)]
DP[0][0]=0

for i in range(m):
    for j in range(2**n):
        DP[i+1][j] = DP[i][j]
        DP[i+1][j] = min(DP[i+1][j],key[i][0]+DP[i][j-(j&key[i][1])])
if DP[-1][-1]==float('inf'):
    print(-1)
else:
    print(DP[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
DP = [[10**9]*(2**N)for i in range(M+1)]
DP[0][0] = 0
key = []
for i in range(M):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    rock = 0
    for j in c:
        rock += 2**(j-1)
    key.append([a,rock])
for i in range(M):
    for j in range(2**N):
        DP[i+1][j] = DP[i][j]
        DP[i+1][j] = min(DP[i+1][j],key[i][0]+DP[i][j - (j&key[i][1])])
ans = DP[-1][-1]
if ans >= 10**9:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
inf = np.inf
N, M = list(map(int, input().split(" ")))
keys = []
for _ in range(M):
	c = list(map(int, input().split(" ")))
	j = list(map(int, input().split(" ")))
	keys.append([c[0], np.sum([1 << k-1 for k in j])])
dp = [inf for _ in range(1 << N)]
dp[0] = 0
for i in range(len(dp)):
    for key in keys:
        t = i | key[1]
        dp[t] = min(dp[t], key[0] + dp[i])
if dp[-1]==inf:
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
from numpy import inf
N, M = list(map(int, input().split(" ")))
keys = []
for _ in range(M):
	c = list(map(int, input().split(" ")))
	j = list(map(int, input().split(" ")))
	keys.append([c[0], sum([1 << k-1 for k in j])])
dp = [inf for _ in range(1 << N)]
dp[0] = 0
for i in range(len(dp)):
    for key in keys:
        t = i | key[1]
        dp[t] = min(dp[t], key[0] + dp[i])
if dp[-1]==inf:
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

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

INF = 1<<32
    
def solve(N: int, M: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    dp = [[INF] * ((1<<N)+1) for i in range(M+1)]
    # for i in map(bin, c):
    #     print(i)

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

    # for i in dp:
    #     print(i)
    print(dp[M][(1<<N)-1] if (dp[M][(1<<N)-1]) < INF else -1)


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    N, M = map(int, input().split())
    a = []
    b = []
    c = []
    for i in range(M):
        ax, bx = map(int, input().split())
        cx = map(int, input().split())
        a.append(ax)
        b.append(bx)
        ct = 0
        for j in cx:
            ct |= (1<<(j-1))
        c.append(ct)
    solve(N, M, a, b, c)

    
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def main():
    # bit DP
    N, M = map(int, input().split())
    a, b, c, d = [], [], [], []

    for i in range(M):
        a_, b_ = map(int, input().split())
        c_ = tuple(map(int, input().split()))
        d_ = 0
        for keta in c_:
            d_ |= 1 << keta-1
        a.append(a_)
        b.append(b_)
        c.append(c_)
        d.append(d_)

    DP = [INF]*(2**N)
    DP[0] = 0

    for i in range(M):
        DPnext = DP[:]
        for k in range(2**N):
            DPnext[k | d[i]] = min(DP[k | d[i]], DP[k]+a[i], DPnext[k | d[i]])
        DP = DPnext
    if DP[-1] == INF:
        print(-1)
    else:
        print(DP[-1])
    pass


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
Dp = [10**10]*(2**N)
Dp[0] = 0

for i in range(M): #カギiで
    a,_=map(int, input().split())
    c = list(map(int, input().split()))
    d = sum((1<<p-1) for p in c) #iで開けられる宝箱の2bit表記
    for j in range(2**N):
        ope = j|d
        Dp[ope] = min(Dp[ope], Dp[j] + a)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = int(1e10)
n, m = [int(i) for i in sys.stdin.readline().split()]
# n : box, m : key
key_info = dict()
for i in range(m):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    c_ls = [int(i)-1 for i in sys.stdin.readline().split()]
    c_ls = "".join(["1" if c in c_ls else "0" for c in range(n-1,-1,-1)])
    key_info[i] = [a, int(c_ls, 2)]

memo_ls = [[INF for i in range(2**n)] for j in range(m)]
# memo_ls[i][j] : i番目までの鍵で状態を j にする為に必要な最小費用
for i in range(m):
    memo_ls[i][0] = 0
    for j in range(2**n):
        memo_ls[i][j] = min(memo_ls[i][j], memo_ls[max(0, i-1)][j])
        memo_ls[i][j | key_info[i][1]] = min(memo_ls[i][j | key_info[i][1]], memo_ls[max(i-1, 0)][j | key_info[i][1]], memo_ls[max(0, i-1)][j] + key_info[i][0])
if memo_ls[-1][-1] == INF:
    print(-1)
else:
    print(memo_ls[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a, b, c = [], [], []
for _ in range(M):
    a_, b_ = map(int, input().split())
    c_ = list( map(int, input().split()) )
    a.append(a_)
    b.append(b_)
    c.append(c_)

exist = [0, 1]
box = set([ i for i in range( 1, N+1 ) ])
minCost = 10**9
for key in range( 1, (1<<M)+1 ):
    openBox = set([])
    price = 0
    for i in range(M):
        if ((key>>i) & 1)==1:
            openBox |= set(c[i])
            price += a[i]
            if price > minCost: continue
    if openBox == box and price <= minCost:
        minCost = price

res = minCost if minCost < 10**9 else -1
print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N, M = map(int, input().split())
a, b, c = [], [], []
for _ in range(M):
    a_, b_ = map(int, input().split())
    c_ = list( map(int, input().split()) )
    a.append(a_)
    b.append(b_)
    c.append(c_)

exist = [0, 1]
box = set([ i for i in range( 1, N+1 ) ])
minCost = 10**9
for key in range( 1, (1<<M)+1 ):
    openBox = set([])
    price = 0
    for i in range(M):
        if ((key>>i) & 1)==1:
            openBox |= set(c[i])
            price += a[i]
    if openBox == box and price <= minCost:
        minCost = price

res = minCost if minCost < 10**9 else -1
print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
N, M=map(int, input().split())
a =[]
c = []
for i in range(2*M):
  if i%2 == 0:
    temp,_=map(int, input().split()) 
    a.append(temp)
  else:
    temp=list(map(int, input().split()))
    c.append(temp)
a = np.array(a) 

row = 2**M 
boo = np.array([[int(j[i]) for i in range(M)] for j in  [bin(i)[2:].zfill(M) for i in range(row)]])
table = np.zeros((row,N), dtype = 'int8')

for i in range(row):
    ind_temp = np.array(list(set(itertools.chain.from_iterable(c*boo[i]))),dtype = int) -1
    table[i][ind_temp] = 1

ind = np.where(np.all(table, axis=1))
price = np.array([np.sum(a*boo[ind], axis = 1)])

if price.any():
    print(np.min(price))
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
N, M=map(int, input().split())
a =[]
c = []
for i in range(2*M):
  if i%2 == 0:
    temp,_=map(int, input().split()) 
    a.append(temp)
  else:
    temp=list(map(int, input().split()))
    c.append(temp)
a = np.array(a) 
mini = -1

for n in range(M):
    for l in list(itertools.combinations(range(M),n+1)):
        temp = [c[nn] for nn in l]
        temp = set(itertools.chain.from_iterable(temp))
        if len(temp) == N:
            cost = sum(a[[np.array(l)]])
            if mini == -1 or mini > cost:
                mini = cost

print(mini)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
N, M=map(int, input().split())
a =[]
c = []
for i in range(2*M):
  if i%2 == 0:
    temp,_=map(int, input().split()) 
    a.append(temp)
  else:
    temp=list(map(int, input().split()))
    c.append(temp)
a = np.array(a) 
mini = -1
for n in range(M):
    for l in list(itertools.combinations(range(M),n+1)):
        temp = []
        for nn in l:
            temp = temp +c[nn]
        temp = set(temp)
        temp = list(temp)
        if len(temp) == N:
            cost = sum(a[[np.array(l)]])
            if mini == -1 or mini > cost:
                mini = cost


print(mini)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
N, M=map(int, input().split())
a =[]
c = []
for i in range(2*M):
  if i%2 == 0:
    temp,_=map(int, input().split()) 
    a.append(temp)
  else:
    temp=list(map(int, input().split()))
    c.append(temp)
a = np.array(a) 
mini = -1
for n in range(M):
    for l in list(itertools.combinations(range(M),n+1)):
        temp = []
        for nn in range(len(l)):
            temp = temp +c[l[nn]]
        temp = set(temp)
        temp = list(temp)
        if len(temp) == N:
            cost = sum(a[[np.array(l)]])
            if mini == -1 or mini > cost:
                mini = cost


print(mini)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
AB_C = [[list(map(int, input().split())) for _ in range(2)] for _ in range(M)]

keys = []
for i, ((a, b), c) in enumerate(AB_C):
    key_flag = 0
    for c_i in c:
        key_flag |= 1<<(c_i-1)
    keys.append((a, key_flag))

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

for i, (price, flag) in enumerate(keys):
    for j in range(1<<N):
        dp[i+1][j] = min(
            dp[i+1][j],
            dp[i][j]
        )
        dp[i+1][j|flag] = min(
            dp[i+1][j|flag],
            dp[i+1][j] + price
        )

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

Submission status: Time Limit Exceeded

Solution code:

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

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

for j in range(M):
    a, b = map(int, input().split())
    box = list(map(int, input().split()))
    for i in range(1 << N):
        now_status = i
        score = C[now_status] + a
        if score == float("inf"):
            continue

        ex_status = 0
        for j in box:
            ex_status += 1 << (j-1)
        now_status = i | ex_status

        if C[now_status] > score:
            C[now_status] = score

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

Submission status: Time Limit Exceeded

Solution code:

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

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

for j in range(M):
    a, b = map(int, input().split())
    box = list(map(int, input().split()))
    for i in range(1 << N):
        now_status = i
        score = C[now_status] + a

        ex_status = 0
        for j in box:
            ex_status += 1 << (j-1)
        now_status = i | ex_status

        if C[now_status] > score:
            C[now_status] = score

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

Submission status: Time Limit Exceeded

Solution code:

N, M = map(int, input().split())
C = {}
for i in range(1 << N):
    C[format(i, "012b")[::-1]] = 10**9
C["000000000000"] = 0
keys = []

for j in range(M):
    a, b = map(int, input().split())
    box = list(map(int, input().split()))
    for i in range(1 << N):
        now_status = format(i, "012b")[::-1]
        score = C[now_status] + a

        ex_status = list(now_status)
        for j in box:
            ex_status[j-1] = "1"
        now_status = "".join(ex_status)

        if C[now_status] > score:
            C[now_status] = score

if C["1"*N+"0"*(12-N)] == 10**9:
    print(-1)
else:
    print(C["1"*N+"0"*(12-N)])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N, M = map(int, input().split())
keys = []
for i in range(M):
    a, b = map(int, input().split())
    keys.append((a, list(map(int, input().split()))))
C = Counter()
for i in range(1 << N):
    C[format(i, "012b")[::-1]] = 10**9
C["000000000000"] = 0
for a, b in keys:
    for i in range(1 << N):
        now_status = format(i, "012b")[::-1]
        score = C[now_status] + a

        ex_status = list(now_status)
        for j in b:
            ex_status[j-1] = "1"
        now_status = "".join(ex_status)

        if C[now_status] > score:
            C[now_status] = score

if C["1"*N+"0"*(12-N)] == 10**9:
    print(-1)
else:
    print(C["1"*N+"0"*(12-N)])

Submission status: Time Limit Exceeded

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

A = []
C = []
for _ in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    A.append(a)
    C.append(c)

def locked(box, c):
    for cc in c:
        if box[cc - 1]:
            return True
    return False

def unlock(box, c):
    newbox = box[:]
    for cc in c:
        newbox[cc - 1] = False
    return newbox

def finished(box):
    for x in box:
        if x:
            return False
    return True

answers = []

def f(box, cost):
    if finished(box):
        answers.append(cost)
        return
    if len(answers) > 0 and cost >= min(answers):
        return
    for a, c in zip(A, C):
        if locked(box, c):
            newbox = unlock(box, c)
            if newbox != box:
                f(newbox, cost + a)

box = [True for _ in range(N)]
f(box, 0)
if len(answers) > 0:
    print(min(answers))
else:
    print(-1)

Submission status: Time Limit Exceeded

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

A = []
C = []
for _ in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    A.append(a)
    C.append(c)

def locked(box, c):
    for cc in c:
        if box[cc - 1]:
            return True
    return False

def unlock(box, c):
    newbox = box[:]
    for cc in c:
        newbox[cc - 1] = False
    return newbox

def finished(box):
    for x in box:
        if x:
            return False
    return True

answers = []

def f(box, cost):
    if finished(box):
        answers.append(cost)
    for a, c in zip(A, C):
        if locked(box, c):
            newbox = unlock(box, c)
            if newbox != box:
                f(newbox, cost + a)

box = [True for _ in range(N)]
f(box, 0)
if len(answers) > 0:
    print(min(answers))
else:
    print(-1)

Submission status: Time Limit Exceeded

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

N, M = map(int,input().split())
a = []
c = []
for i in range(M):
    a_,b=map(int,input().split())
    a.append(a_)
    c_tmp = list(map(int, input().split()))
    tmp=0
    for j in range(len(c_tmp)):
        tmp+=2**(c_tmp[j]-1)
    c.append(tmp)
INF = N*1e+6
dp = [INF]*2**N
dp[0]=0

for i in range(2**N):
    for j in range(M):
        dp[i|c[j]]=min(dp[i|c[j]], dp[i]+a[j])
if dp[2**N-1]==INF:
    print(-1)
    sys.exit()
print(dp[2**N-1])

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ac_lst = []
for i in range(m):
    a, b = map(int, input().split())
    lst = list(map(int, input().split()))
    ac_lst.append((a, lst))
    
dp = [[10**10] * (2**n) for _ in range(m+1) ]
for i in range(m+1):
    dp[i][0] = 0

for i in range(1, m+1):
    a, c_lst = ac_lst[i-1]
    d = 0
    for k in c_lst:
        d = d | (2**(k-1))
    for j in range(2**n):
        k = j | d
        dp[i][j] = min(dp[i][j], dp[i-1][j])
        dp[i][k] = min(dp[i][k], dp[i-1][k], dp[i-1][j] + a)
        
print(dp[-1][-1]) if dp[-1][-1] != 10**10 else print(-1)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys

[N,M] = list(map(int,input().split()))

keyset = (1 << N) - 1
keys = []

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

    boxes  = list(map(int,input().split()))
    for box in boxes:
        key |= (1 << (box-1))
    keys.append((a,key))

def getEdges(node):
    edges = []
    for (a, key) in keys:
        edges.append( (a, ((node ^ key) & node) & keyset))
    return edges


"""
    shortest path from 111111 -> 00000000
    treat each 2^N-1 value as a node
    edges directed graph (00) -> 0 (01) -> 0 (10) -> 1 (11) -> 0
"""

heap = [(0, keyset)]
seen = set()
while heap:
    (dist, node) = heapq.heappop(heap)
    seen.add(node)
    if node == 0:
        print(dist)
        sys.exit(0)
    for (w, v)  in getEdges(node):
        if v not in seen:
            heapq.heappush(heap, (dist+w, v))
print(-1)

Submission status: Time Limit Exceeded

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

n,m=map(int,input().split())
inf=10**9+7
dp=[inf]*(2**n)
dp[0]=0

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False

def ddprint(x):
  if DBG:
    print(x)

BIG = 999999


# # # # main start

n,m = inm()
fff = 2**n - 1
dp = [BIG] * (2**n)
a = []
s = []
for i in range(m):
  aa,bb = inm()
  c = inl()
  ss = 0
  c = [x-1 for x in c]
  for cc in c:
    ss |= (1<<cc)
  a.append(aa)
  s.append(ss)

dp = [BIG] * (2**n)
dp[0] = 0

for i in range(m):
  aa = a[i]
  ss = s[i]
  for j in range(2**n):
    dp[j|ss] = min(dp[j|ss], dp[j]+aa)

v = dp[2**n-1]
print(-1 if v>=BIG else v)

Submission status: Time Limit Exceeded

Solution code:
import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False

def ddprint(x):
  if DBG:
    print(x)

BIG = 999999

def dfs(bx, s, v):
  ddprint("dfs bx {} s {} v {}".format(bx,s,v))
  if s == fff:
    if v<dp[fff]:
      dp[fff] = v
    return dp[fff]
  if bx>=n:
    return BIG
  if v>=dp[s]:
    return dp[fff]
  bit = (1<<bx)
  if bit|s == s:
    return dfs(bx+1,s,v)
  mn = BIG
  for z in box[bx]:
    val = z[1]
    addset = z[2]
    ddprint("call newi {} newset {} newv {}".format(i+1, s|addset, v+val))
    newval = dfs(bx+1, s|addset, v+val)
    mn = min(mn, newval)
  return mn

# # # # main start

n,m = inm()
fff = 2**n - 1
dp = [BIG] * (2**n)
key = []
box = [ [] for i in range(n) ]
for i in range(m):
  a,b = inm()
  c = inl()
  s = 0
  c = [x-1 for x in c]
  for cc in c:
    s |= (1<<cc)
  v = a/len(c)
  key.append((v,a,b,c,s))
  for bx in c:
    box[bx].append((v,a,s,i))  # prio,val,set,suf

for z in box:
  z.sort()
  ddprint(z)

v = dfs(0,0,0)
print(-1 if v>=BIG else v)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  a = [None]*(m+1)
  b = [None]*(m+1)
  takara = [0]*m
  for i in range(m):
    ta,tb = (int(i) for i in input().split())
    a[i] = ta
    b[i] = tb
    c = list(int(i) for i in input().split())
    for j in c:
      tmp = j-1
      takara[i] += 1<<tmp
  inf = float("Inf")
  dp = [[inf]*(2**n+1) for _ in range(m+1)]
  dp[0][0] = 0
  for i in range(m):
    for j in range(2**n):
      dp[i+1][j] = min(dp[i][j],dp[i+1][j])
      dp[i+1][j|takara[i]] = min(dp[i][j]+a[i],dp[i+1][j|takara[i]])
  if not dp[m][2**n-1] == inf:
    print(dp[m][2**n-1])
  else:
    print(-1)
solve()

Submission status: Time Limit Exceeded

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

inf = 10**9

dp = [[inf for _ in range(2**n)]] * m
dp[0][0] = 0

for i in range(m):
    a,b = map(int, input().split())
    d = sum((1<<(i-1)) for i in map(int, input().split()))
  
    #initialize
    if i==0:
        dp[0][d] = a
        continue
        
    for j in range(2**n):
        jord = j | d
        dp[i][jord] = min(dp[i-1][jord], dp[i-1][j] + a, dp[i][jord])
            
if dp[m-1][2**n-1] == inf:
    print(-1)
else:
    print(dp[m-1][2**n-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return [int(i)-1 for i in input().split()]
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    ans = 0
    for i in range(1, n + 1):
        ans += i & 1
    print(ans/n)
    return

#B
def B():
    n, k = LI()
    h = LI()
    ans = 0
    for i in h:
        ans += i >= k
    print(ans)
    return

#C
def C():
    n = II()
    a = LI()
    d = defaultdict(int)
    for i in range(n):
        d[a[i] + 1] = i + 1
    for _, v in sorted(d.items()):
        print(v, end=" ")
    print()
    return

def primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    """ 6以上の数であれば p (素数) <= n のlistを返す """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

#D
def D():
    a, b = LI()
    da = defaultdict(int)
    db = defaultdict(int)
    for i in range(2, int(math.sqrt(a)) + 1):
        while a % i == 0:
            a = a // i
            da[i] = 1
        while b % i == 0:
            b = b // i
            db[i] = 1
    da[a] = 1
    db[b] = 1
    da[1] = 1
    db[1] = 1
    print(len(set(da.keys()) & set(db.keys())))
    return

#E
def E():
    n, m = LI()
    dp = [inf] * (1 << n)
    dp[0] = 0
    for _ in range(m):
        a, b = LI()
        c = LI_()
        fulls = [i for i in itertools.product(range(2), repeat=b)]
        for i in range(1 << n):
            for full in fulls:
                tmp = 0
                for k, f in enumerate(full):
                    if f:
                        tmp |= 1 << c[k]
                dp[i | tmp] = min(dp[i | tmp], dp[i] + a)
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Time Limit Exceeded

Solution code:
import math
N, M = list(map(int, input().split(" ")))
abc = [[0, 0, 0] for i in range(M)]
for i in range(M):
  abc[i][0], abc[i][1] = list(map(int, input().split(" ")))
  c = list(map(int, input().split(" ")))
  for j in range(N):
    cbits = (1 << j) * (j+1 in c)
    abc[i][2] |= cbits

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
INF = 10**10
def solve(n, m, a, b, C):
    dp = np.full((m+1, 2**n), INF, dtype=int)
    x = np.zeros(m, dtype=int)
    for i in range(m):
        mask = 0
        for c in C[i]:
            mask |= 2 ** (c - 1)
        x[i] = mask
    dp[:,0] = 0
    for i in range(m):
        for mask in range(2**n):
            dp[i+1][mask] = min(dp[i+1][mask], dp[i][mask])
            s = mask | x[i]
            dp[i+1][s] = min(dp[i+1][s], dp[i][mask] + a[i])
    best = dp[m][2**n-1]
    return -1 if best == INF else best

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
C = []
for i in range(m):
    a[i], b[i] = map(int, input().split())
    c = list(map(int, input().split()))
    C.append(c)
print(solve(n, m, a, b, C))