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: Wrong Answer

Solution code:
from collections import defaultdict

d=defaultdict(list)

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

for i in range(m):
  a,b=map(int,input().split())
  c=list(map(int,input().split()))
  for j in range(b):
    d[c[j]]+=[(a,i+1)]

ans=0
key=set()
if len(d)!=n:
  print(-1)
  exit(0)

for k,li in d.items():
  li.sort(key=lambda x:x[0])
  if li[0][1] in key:
    pass
  else:
    ans+=li[0][0]
    key.add(li[0][1])
    
print(ans)

Submission status: Wrong Answer

Solution code:
# ABC141e
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

takara = [[-1, -1] for _ in range(n + 1)]


for i in kagi:
    for j in i[2]:
        if (takara[j][0] == -1 or i[0]/i[1] < takara[j][0]):
            takara[j][0] = i[0]/i[1]
            takara[j][1] = i[3]
# print(takara)
used = set()
ans = 0
for i in range(1, len(takara)):
    if takara[i][1] == -1:
        print(-1)
        exit()
    if not takara[i][1] in used:
        ans += kagi[takara[i][1]][0]
        used.add(takara[i][1])
print(ans)

Submission status: Wrong Answer

Solution code:
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())
    ci = list(map(int, input().split()))
    c.append(ci)


flag = False
ans = 100000000000000

for i in range(1 << m):
    ls = []
    money = 0
    for j in range(m):
        if(1 << j & i):
            money += a[j]
            for ci in c[j]:
                ls.append(ci)
            ls = list(set(ls))
    if(len(ls) == n):
        ans = min(ans, money)
        flag = True

if(flag):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n, m = [int(x) for x in input().split()]

key_prices_boxes = []
for _ in range(m):
  price = [int(x) for x in input().split()][0]
  boxes = [int(x) for x in input().split()]
  key_prices_boxes.append((price, boxes))

result = {i+1: (None, ) for i in range(n)}

for keyidx, (price, boxes) in enumerate(key_prices_boxes):
  for box in boxes:
    if (result[box][0] is None) or (price < result[box][1]):
      result[box] = (keyidx, price)

if any([r[0] is None for r in result.values()]):
  print(-1)
else:
  resprice = 0
  keycache = []
  for keyidx, price in result.values():
    if keyidx in keycache:
      continue
    keycache.append(keyidx)
    resprice += price
  print(resprice)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
dp = [[int(2e8) for _ in range(2**n)] for _ in range(2)]
dp[0][0] = 0
dp[1][0] = 0
for i in range(m):
    a, _ = map(int, input().split())
    k = sum(map(lambda c: 1 << (c - 1), list(map(int, input().split()))))
    for j in range(2**n):
         dp[(i + 1) % 2][j | k] = min(dp[(i + 1) % 2][j | k], dp[i % 2][j] + a)
ans = dp[n % 2][2**n - 1]
if ans == int(2e8):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
NL = [0 for i in range(N)]
ABC = []
ans = 0
for i in range(M):
    ai,bi = map(int,input().split())
    ci = list(map(int,input().split()))
    for j in range(len(ci)):
        ci[j] -= 1
        NL[ci[j]] += 1
    ans += ai
    ABC.append([ai,bi,ci])
if 0 in NL:
    print(-1)
else:
    ABC.sort(key=lambda x: x[1])
    ABC.sort(key=lambda x: x[0],reverse=True)

    for i in range(M):
        use = False
        for j in range(len(ABC[i][2])):
            if NL[ABC[i][2][j]] == 1:
                use = True
                break
        if use:
            pass
        else:
            ans -= ABC[i][0]
            for j in range(len(ABC[i][2])):
                NL[ABC[i][2][j]] -= 1

    print(ans)

Submission status: Wrong Answer

Solution code:
import math
import heapq
from bisect import bisect_right, bisect_left
from collections import defaultdict, Counter
import itertools
import sys
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7
INF = float("inf")

def main():
    n, m = map(int, input().split())
    d = defaultdict(lambda: float("inf"))
    ind = defaultdict(int)
    ivalue = defaultdict(int)
    c = []
    for i in range(m):
        a, b = map(int, input().split())
        l = list(map(int,input().split()))
        for j in range(b):
            if a < d[l[j]]:
                d[l[j]] = a
                ind[l[j]] = i
            c.append(l[j])
    c = list(set(c))
    if len(c) != n:
        print(-1)
        exit()
    ans = 0

    alr = defaultdict(int)
    for i in range(1 , n+1):
        if alr[ind[i]] == 0:
            #print(i,d[i])
            ans += d[i]
            alr[ind[i]] = 1



    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
NL = [0 for i in range(N)]
ABC = []
ans = 0
for i in range(M):
    ai,bi = map(int,input().split())
    ci = list(map(int,input().split()))
    for j in range(len(ci)):
        ci[j] -= 1
        NL[ci[j]] += 1
    ans += ai
    ABC.append([ai,bi,ci])

ABC.sort(key=lambda x: x[1])
ABC.sort(key=lambda x: x[0],reverse=True)

for i in range(M):
    use = False
    for j in range(len(ABC[i][2])):
        if NL[ABC[i][2][j]] == 1:
            use = True
            break
    if use:
        pass
    else:
        ans -= ABC[i][0]
        for j in range(len(ABC[i][2])):
            NL[ABC[i][2][j]] -= 1
if 0 in NL:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)
from itertools import permutations

def solve(N, M, a, b, c):
    tmp = []
    for i in range(M):
        for j in c[i]:
            tmp.append([a[i], i])
    tmp.sort()
    ret = 0
    opened = [False] * N
    for t in tmp:
        s = t[0]
        idx = t[1]
        use = False
        for v in c[idx]:
            if not opened[v - 1]:
                use = True
                opened[v - 1] = True
        if use:
            ret += s
    for o in opened:
        if not o:
            print(-1)
            return
    print(ret)
    return

def solve_(N, M, a, b, c):
    tmp = [[] for _ in range(N)]
    for i in range(M):
        for j in c[i]:
            tmp[j - 1].append([a[i], i])
    for i in range(N):
        if len(tmp[i]) < 1:
            print(-1)
            return
        tmp[i].sort()
    perms = list(permutations(list(range(N))))
    ret = float('inf')
    for o in perms:
        s = 0
        opened = [False] * N
        for i in o:
            if not opened[i]:
                t = tmp[i][0]
                s += t[0]
                idx = t[1]
                for v in c[idx]:
                    opened[v - 1] = True
        ret = min(ret, s)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = []
    b = []
    c = []
    for i in range(M):
        A = int(next(tokens))  # type: int
        B = int(next(tokens))  # type: int
        a.append(A)
        b.append(B)
        c.append([ int(next(tokens)) for _ in range(B) ])
    solve(N, M, a, b, c)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#%%
N, M = map(int, input().split())
a = [0] * M
b = [0] * 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()))


import itertools
l = list(itertools.product(range(2), repeat=12))

key = [10**6] * (2**12) 

for i in range(M):
    tmp = [0] * 12
    for j in range(b[i]):
        tmp[c[i][j]-1] =1
    w = 0
    for j in range(12):
        w += 2 ** (11-j) * tmp[j]
    key[w] = min(key[w], a[i])

print(1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
c=[0]*(2000)
dp=[10**19]*(n+1)
dp[0]=0 
for i in range(m): 
    c[i],k=map(int,input().split())
    z=[int(i) for i in input().split()]
    if all(dp[x]!=10**19 for x in z):
        sm=sum(dp[x] for x in z)
        now=c[i]
        if now<sm: 
            for x in z:
                dp[x]=now 
    else: 
        for x in z:
            dp[x]=c[i]
f=1 
sm=set()
for i in range(1,n+1):
    if dp[i]==10**19:
        f=0 
    sm.add(dp[i])
#print(dp)
if f:
    print(sum(sm))
    
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    INF = 1e10
    table = np.full((M, N), INF)
    ab = []
    for i in range(M):
        a, b = map(int, input().split())
        ab.append((a, b))
        c = np.array(list(map(int, input().split())))
        table[i][c-1] = a/b
    
    ans = 0
    ok = True
    check = [False] * N
    for i in range(N):
        if not check[i]:
            check[i] = True
            d = np.argmin(table[:,i])
            if table[d][i] == INF:
                ok = False
                break
            for j in range(N):
                if table[d][j] != INF:
                    check[j] = True
            ans += ab[d][0]
    
    if ok:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def solve():
  n,m = (int(i) for i in input().split())
  c = []
  buy = [False]*n
  for i in range(m):
    a,b = (int(i) for i in input().split())
    tmp = list(int(i) for i in input().split())
    c.append(((a/b,a),tmp))
  c.sort()
  c = deque(c)
  ans = 0
  while c:
    info,key = c.popleft()
    scrap,value = info
    for i in range(len(key)):
      buy[key[i]-1] = True
    ans += value
    #更新
    newc = []
    for i in range(len(c)):
      gomib,key = c[i]
      gomib,a = gomib
      newb = 0
      for i in range(len(key)):
        tmp = key[i]-1
        if not buy[tmp]:
          newb += 1
      if newb != 0:
        newc.append(((a/newb,a),key))
    newc.sort()
    c = deque(newc)
  judge = 1
  for i in range(n):
    if not buy[i]:
      print("-1")
      exit()
  print(ans)
solve()

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, _ = map(int, input().split())
    c = set(map(int, input().split()))
    keys.append([a, c])

ans = float('inf')
for b in range(2**N):
    opened = set()
    money = 0
    for key in range(M):
        if (b >> key) & 1:  # key番目の鍵を買う
            money += keys[key][0]
            opened |= keys[key][1]
        if len(opened) == N:
            break
    if len(opened) == N:
        ans = min(ans, money)
if ans == float('inf'):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)
from itertools import permutations

def solve(N, M, a, b, c):
    tmp = [[] for _ in range(N)]
    for i in range(M):
        for j in c[i]:
            tmp[j - 1].append([a[i], i])
    for i in range(N):
        if len(tmp[i]) < 1:
            print(-1)
            return
        tmp[i].sort()
    perms = list(permutations(list(range(N))))
    ret = float('inf')
    for o in perms:
        s = 0
        opened = [False] * N
        for i in o:
            if not opened[i]:
                t = tmp[i][0]
                s += t[0]
                idx = t[1]
                for v in c[idx]:
                    opened[v - 1] = True
        ret = min(ret, s)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = []
    b = []
    c = []
    for i in range(M):
        A = int(next(tokens))  # type: int
        B = int(next(tokens))  # type: int
        a.append(A)
        b.append(B)
        c.append([ int(next(tokens)) for _ in range(B) ])
    solve(N, M, a, b, c)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
res = [[] for i in range(m)]
val = [0] * m
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    for j in range(len(c)):
        res[i].append(c[j])
    val[i] = a



# i番目まで鍵を見たときにbit_stateの状態になっているときの最小値
INF = 10**9 + 7
dp  = [[INF]*(2**n) for i in range(m + 1)]
dp[0][0] = 0
for i in range(m):
    mask = 0
    for j in res[i]:
        mask += 2**(j-1)
    for bit_state in range(2**n):
        # i番目の鍵を使わない時
        dp[i+1][bit_state] = min(dp[i+1][bit_state], dp[i][bit_state])
        # i番目の鍵を使う時
        dp[i+1][bit_state | mask] = min(dp[i+1][bit_state | mask], dp[i][bit_state] + val[i])
print(dp[-1][-1])

Submission status: Wrong Answer

Solution code:
#E問題
N,M = map(int,input().split())
ABC = []
for i in range(M):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    ABC.append([a,b,c])
    
keys = [[] for i in range(N)]
for i in range(M):
    a,b,c = ABC[i]
    for cs in c:
        keys[cs-1].append(i)
        
MIN = 10**9
if [] in keys:
    print(-1)
else:
    bit = 2**N
    for i in range(bit):
        b = bin(i)
        b = b.lstrip("0b")
        blen = len(b)
        for j in range(N-blen):
            b = "0" + b
            
        kari = 0
        used = [0 for j in range(N)]
        for k in range(N):
            if b[k] == "1":
                kari+=ABC[k][0]
                for c in ABC[k][2]:
                    used[c-1]+=1
                    
        if 0 not in used:
            MIN = min(MIN,kari)
                
    print(MIN)

Submission status: Wrong Answer

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

dp = [float("inf")]*(2**n)
for _ in range(m):
    a,b = map(int,input().split())
    c = tuple(map(int,input().split()))
    jkl = 0
    for e in c:
        jkl += 1 << (e-1)
    dp[jkl] = min(dp[jkl],a)

tank = []
new = [0]
used = [True]*(2**n)

while len(new) != 0:
    tank = []
    for e in new:
        p = []
        q = []
        for i in range(n):
            if (e>>i)&1 == 0:
                p.append(i)
            else:
                q.append(i)
        for ep in p:
            if used[e+(1<<ep)]:
                tank.append(e+(1<<ep))
                used[e+(1<<ep)] = False

        if len(q) <= 1:
            continue
        for i in range(len(q)-1):
            for j in range(i+1,len(q)):
                dp[e] = min(dp[e],dp[e-(1<<i)]+dp[e-(1<<j)])
    new = tank

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

def getval():
    n,m = map(int,input().split())
    ab = []
    c = []
    def tobit(arr):
        idx = len(arr)-1
        s = ""
        for i in range(n-1,-1,-1):
            if arr[idx]-1==i and idx!=-1:
                s = "".join([s,"1"])
                idx -= 1
            else:
                s = "".join([s,"0"])
        return s
    for i in range(m):
        ab.append(list(map(int,stdin.readline().split())))
        c.append(tobit(list(map(int,stdin.readline().split()))))
    return n,m,ab,c 

def main(n,m,ab,c):
    dp0 = [-1 for i in range(2**n)]
    dp1 = [-1 for i in range(2**n)]
    dp0[0] = 0
    dp1[0] = 0
    
    def intersect(bit1,bit2):
        s = ""
        for i in range(n):
            if bit1[i]=="1" or bit2[i]=="1":
                s = "".join([s,"1"])
            else:
                s = "".join([s,"0"])
        return int(s,2)

    for i in range(m):
        curc = ab[i][0]
        curk = c[i]
        temp0 = [-1 for i in range(2**n)]
        temp1 = [-1 for i in range(2**n)]
        for j in range(2**n):
            if dp0[j]==-1 and dp1[j]==-1:
                continue
            new = dp0[j]
            new2 = dp1[j]
            if new==-1 or new2<new:
                if new2!=-1:
                    new = new2
            temp1[j] = new
            s = bin(j)[2:]
            if len(s)!=n:
                while len(s)<n:
                    s = "".join(["0",s])
            update = intersect(curk,s)
            
            #print(i,j,update,new,curc,curk,s)
            target = temp0[update]
            if target==-1:
                temp0[update] = new+curc
            elif target>new+curc:
                temp0[update] = new+curc                
            
        dp0 = temp0
        dp1 = temp1
        #print(dp)
    ans = dp1[2**n-1]
    if ans==-1:
        print(dp0[2**n-1])
    else:
        if ans>dp1[2**n-1] and dp1[2**n-1]!=-1:
            print(dp1[2**n-1])
        else:
            print(ans)  
        
                
if __name__=="__main__":
    n,m,ab,c = getval()
    main(n,m,ab,c)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

def getval():
    n,m = map(int,input().split())
    ab = []
    c = []
    def tobit(arr):
        idx = len(arr)-1
        s = ""
        for i in range(n-1,-1,-1):
            if arr[idx]-1==i and idx!=-1:
                s = "".join([s,"1"])
                idx -= 1
            else:
                s = "".join([s,"0"])
        return s
    for i in range(m):
        ab.append(list(map(int,stdin.readline().split())))
        c.append(tobit(list(map(int,stdin.readline().split()))))
    return n,m,ab,c 

def main(n,m,ab,c):
    dp = [[-1,-1] for i in range(2**n)]
    dp[0] = [0,0]
    
    def intersect(bit1,bit2):
        s = ""
        for i in range(n):
            if bit1[i]=="1" or bit2[i]=="1":
                s = "".join([s,"1"])
            else:
                s = "".join([s,"0"])
        return int(s,2)

    for i in range(m):
        curc = ab[i][0]
        curk = c[i]
        temp = [[-1,-1] for i in range(2**n)]
        for j in range(2**n):
            if dp[j]==[-1,-1]:
                continue
            new = dp[j][0]
            new2 = dp[j][1]
            if new==-1 or new2<new:
                if new2!=-1:
                    new = new2
            temp[j][1] = new
            s = bin(j)[2:]
            if len(s)!=n:
                while len(s)<n:
                    s = "".join(["0",s])
            update = intersect(curk,s)
            
            #print(i,j,update,new,curc,curk,s)
            target = temp[update][0]
            if target==-1:
                temp[update][0] = new+curc
            elif target>new+curc:
                temp[update][0] = new+curc                
            
        dp = temp
        #print(dp)
    ans = dp[2**n-1]
    ans.sort()
    if dp[0]==-1:
        print(ans[1])
    else:
        print(ans[0])   
        
                
if __name__=="__main__":
    n,m,ab,c = getval()
    main(n,m,ab,c)

Submission status: Time Limit Exceeded

Solution code:
def getval():
    n,m = map(int,input().split())
    ab = []
    c = []
    def tobit(arr):
        idx = len(arr)-1
        s = ""
        for i in range(n-1,-1,-1):
            if arr[idx]-1==i and idx!=-1:
                s = "".join([s,"1"])
                idx -= 1
            else:
                s = "".join([s,"0"])
        return s
    for i in range(m):
        ab.append(list(map(int,input().split())))
        c.append(tobit(list(map(int,input().split()))))
    return n,m,ab,c 

def main(n,m,ab,c):
    dp = [[-1,-1] for i in range(2**n)]
    dp[0] = [0,0]
    
    def intersect(bit1,bit2):
        s = ""
        for i in range(n):
            if bit1[i]=="1" or bit2[i]=="1":
                s = "".join([s,"1"])
            else:
                s = "".join([s,"0"])
        return int(s,2)

    for i in range(m):
        curc = ab[i][0]
        curk = c[i]
        temp = [[-1,-1] for i in range(2**n)]
        for j in range(2**n):
            if dp[j]==[-1,-1]:
                continue
            new = dp[j][0]
            if new==-1 or dp[j][1]<new:
                if dp[j][1]!=-1:
                    new = dp[j][1]
            temp[j][1] = new
            s = bin(j)[2:]
            if len(s)!=n:
                while len(s)<n:
                    s = "".join(["0",s])
            update = intersect(curk,s)
            
            #print(i,j,update,new,curc,curk,s)
            if temp[update][0]==-1:
                temp[update][0] = new+curc
            elif temp[update][0]>new+curc:
                temp[update][0] = new+curc                
            
        dp = temp
        #print(dp)
    ans = dp[2**n-1]
    ans.sort()
    if dp[0]==-1:
        print(ans[1])
    else:
        print(ans[0])   
        
                
if __name__=="__main__":
    n,m,ab,c = getval()
    main(n,m,ab,c)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
Cost = []
Key = []
for i in range(M):
    a, b = map(int, input().split())
    Cost.append(a)
    C_ = list(map(int, input().split()))
    C = 0
    for c in C_:
        C += (1 << (c - 1))
    Key.append(C)
ans = float('inf')
for i in range(1 << M):
    a = 0
    X = 0
    for j in range(M):
        if (i >> j) & 1 == 1:
            a += Cost[j]
            X |= Key[j]
    if X == 2 ** N - 1:
        ans = min(ans, a)

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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
dp = [float("inf") for i in range(2 ** n)]
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    for j in range(2 ** b):
        num = 0
        temp = bin(j + 2 ** b)[3:]
        for k in range(b):
            if temp[k] == "1":
                num += 2 ** (c[k] - 1)
        for k in range(2 ** n):
            dp[k | num] = min(dp[k | num], dp[k] + a)
if dp[2 ** n - 1] == float("inf"):
    print(-1)
else:
    print(dp[2 ** n - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    A = []
    C = []
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        A.append(a)
        c = [int(x) for x in input().split()]
        tmp = 0
        for cc in c:
            tmp |= 1 << (cc - 1)

        C.append(tmp)

    dp = [float("inf")] * (2 ** N + 1)

    dp[0] = 0

    for i in range(M):
        for k in range(2 ** N + 1):
            next = C[i] | k
            if next >= (2 ** N + 1):
                continue
            dp[next] = min(dp[next], dp[k] + A[i])

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

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

keys = []

for i in range(M):
    a, b = list(map(int, input().split()))
    key_bit = 0
    c = list(map(int, input().split()))
    for j in range(b):
        key_bit |= 1 << (c[j] - 1)
    keys.append([a, key_bit])

dp = [[math.inf]*(1 << N) for _ in range(M + 1)]

dp[0][0] = 0

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

if dp[M][-1] == math.inf:
    print(-1)
else:
    print(dp[M][-1])

Submission status: Time Limit Exceeded

Solution code:

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

    Cost = [0] * M
    Box_key = [0] * M
    for i in range(M):
        a, b = map(int, input().split())
        Cost[i] = a
        C = list(map(int, input().split()))
        Box_key[i] = sum(1 << (c - 1) for c in C)

    # dp[ i ][ S ] := 最初の i 個の鍵からいくつか選んで、
    # 開いた宝箱の集合が S で表されるような場合についての、最小コスト
    dp = [[INF] * (1 << N) for _ in range(M + 1)]
    dp[0][0] = 0

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

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


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

def unset_nth_bit(num, n):
    return num & ~(1 << n)

def bit(S, j):
    # Sの右からj bit目(0-indexed)
    return (S>>j)&1

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

a = []
c = []
for i in range(M):
    p, q = map(int, input().split())
    a.append(p)
    c.append(list(map(int, input().split())))

dp = [[INF for j in range(1<<N)] for i in range(M+1)]
dp[0][0] = 0


for i in range(M):
    for S in range(1<<N):
        for T in range(1<<len(c[i])):
            SS = S
            for k in range(len(c[i])):
                if bit(T, k):
                    SS = unset_nth_bit(SS, c[i][k]-1)
            dp[i+1][S] = min(dp[i+1][S], dp[i][SS] + a[i])
        dp[i+1][S] = min(dp[i+1][S], dp[i][S])


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

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
dp = [[0]+[10**6] * (2**n-1) for i in range(m+1)]
for i in range(m):
    a, b = map(int, input().split())
    bit = ['0'] * n
    for x in set(map(int, input().split())):
        bit[x-1] = '1'
    bit = int(''.join(bit[::-1]), 2)
    for j, dpnw in enumerate(dp[i]):
        dp[i+1][j] = dpnw
    for j, dpnw in enumerate(dp[i]):
        dp[i+1][j | bit] = min(dp[i+1][j | bit], dp[i][j | bit], a + dpnw)
if dp[m][-1] == 1000000:
    print(-1)
else:
    print(dp[m][-1])

Submission status: Time Limit Exceeded

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

n, m = map(int, input().split())
ac = []
for i in range(m):
    a, b = map(int, input().split())
    tmpc = map(int, input().split())
    c = sum(1 << (ci - 1) for ci in tmpc)
    ac.append((a, c))

# 解説AC
dp = [[0] + [pow(10, 9)] * (pow(2, n) - 1)]
for i, (ai, ci) in enumerate(ac, 1):
    dp.append(dp[-1][:])
    for j in range(pow(2, n)):
        tmp = min(dp[i - 1][j | ci], dp[i - 1][j] + ai)
        dp[i][j | ci] = min(tmp, dp[i][j | ci])
print(-1 if dp[-1][-1] == pow(10, 9) else dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n, m = map(int, input().split())
    price = [0]*m
    typesnum = [0]*m
    types = [[] for _ in range(m)]
    for i in range(m):
        price[i], typesnum[i] = map(int, input().split())
        types[i] = list(map(lambda x: int(x)-1, input().split()))
    dp = [10**9]*(1 << n)
    dp[0]=0
    for bit in range(1 << n):
        for i in range(m):
            keybit = 0
            for op in types[i]:
                keybit |= 1 << op
            dp[bit | keybit] = min(dp[bit | keybit], dp[bit]+price[i])
    if dp[-1] == 10**9:
        dp[-1] = -1
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
d = defaultdict(int)

n,m = map(int, input().split())
d["0"*n] = 0
for i in range(m):
  a,b = map(int, input().split())
  c = list(map(int, input().split()))
  temp=[0]*n
  for i in c:
    temp[i-1] = 1
  t = "".join(str(tt) for tt in temp)
  ks = list(d.keys())
  for key in ks:
    if key != "0"*n and d[key] == 0:
      continue
    t2=""
    for b1, b2 in zip(key, t):
      if b1 == "1" or b2 == "1":
        t2 += "1"
      else:
        t2 += "0"
    if d[t2] == 0:
      d[t2] = d[key] + a
    else:
      d[t2] = min(d[key] + a, d[t2])

ans=d["1"*n]
if ans == 0:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

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

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

for i in range(M):
  a, b = map(int, input().split())
  c = sum(map(lambda x: 1 << (int(x)-1), input().split()))
  for j in range(1<<N):
    k = j|c
    dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    dp[i+1][k] = min(dp[i+1][k], dp[i][k], dp[i][j] + a)

ans = dp[-1][-1]

if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

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

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

for i in range(M):
  a, b = map(int, input().split())
  c = sum(map(lambda x: 1 << (int(x)-1), input().split()))
  for j in range(1<<N):
    dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    dp[i+1][j|c] = min(dp[i+1][j|c], dp[i][j|c], dp[i][j] + a)

ans = dp[-1][-1]

if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Time Limit Exceeded

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