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:
N, M = map(int, input().split())
ls = []
dp = [float('inf')]*(1<<N)
for i in range(M):
  a, b = map(int, input().split())
  c = ['0']*N
  inf = [int(i)-1 for i in input().split()]
  for i in range(b):
    x = inf[i]
    c[x] = '1'
  m = ''.join(c)
  m = int(m,2)
  ls += [(a,m)]
  dp[m] = a
dp[0] = 0
for i in range(1<<N):
  for j in range(1<<N):
    dp[i|j] = min(dp[i|j], dp[i]+dp[j])
ans = dp[-1] if dp[-1]!=float('inf') else -1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ls = []
dp = [float('inf')]*(1<<N)
for i in range(M):
  a, b = map(int, input().split())
  c = ['0']*N
  inf = [int(i)-1 for i in input().split()]
  for i in range(b):
    x = inf[i]
    c[x] = '1'
  m = ''.join(c)
  m = int(m,2)
  ls += [(a,m)]
  dp[m] = a
for i in range(1<<N):
  for j in range(1<<N):
    dp[i|j] = min(dp[i|j], dp[i]+dp[j])
ans = dp[-1] if dp[-1]!=float('inf') else -1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ls = []
dp = [float('inf')]*(1<<N)
for i in range(M):
  a, b = map(int, input().split())
  c = ['0']*N
  inf = [int(i)-1 for i in input().split()]
  for i in range(b):
    x = inf[i]
    c[x] = '1'
  m = ''.join(c)
  m = int(m,2)
  ls += [(a,m)]
dp[0] = 0
for i in range(1<<N):
  for j in range(i+1,1<<N):
    dp[i|j] = min(dp[i|j], dp[i]+dp[j])
ans = dp[-1] if dp[-1]!=float('inf') else -1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ls = []
dp = [float('inf')]*(1<<N)
for i in range(M):
  a, b = map(int, input().split())
  c = ['0']*N
  inf = [int(i)-1 for i in input().split()]
  for i in range(b):
    x = inf[i]
    c[x] = '1'
  m = ''.join(c)
  m = int(m,2)
  ls += [(a,m)]
  dp[m] = a
for i in range(1<<N):
  for j in range(i+1,1<<N):
    dp[i|j] = min(dp[i|j], dp[i]+dp[j])

ans = dp[-1] if dp[-1]!=float('inf') else -1
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import *
N,M=map(int,input().split())
kagi=[]
for i in range(M):
    a,b=map(int,input().split())
    C=list(map(int,input().split()))
    for i in range(b):
        C[i]-=1
    kagi.append([a,set(C)])

value=10**7
idx=-1
for i in range(M):
    if 0 in kagi[i][1] and kagi[i][0]<value:
        value=kagi[i][0]
        idx=i
if idx==-1:
    print(-1)
    exit()
kagilst=[idx]

takara=[set() for i in range(N)]
for m in range(M):
    for k in kagi[m][1]:
        takara[k].add(m)
for n in range(1,N):
    tempkagi=-1
    tempvalue=10**7

    for k in takara[n]:
        kagilst.append(k)

        for i in range(len(kagilst)**2):

            lst=[0 for i in range(n+1)]

            A=bin(i)[2:]

            A=list(reversed(list(A)))
            for i in range(len(kagilst)-len(A)):
                A.append("0")
            for a in range(len(kagilst)):
                if A[a]=="1":
                    for h in kagi[kagilst[a]][1]:
                        if h<len(lst):
                            lst[h]=1
            temptempvalue=sum([kagi[kagilst[a]][0] for a in range(len(kagilst)) if A[a]=="1"])
            if not 0 in lst:
                if temptempvalue<tempvalue:
                    tempvalue=temptempvalue
                    tempkagi=kagilst[-1]
        kagilst.pop()
    if tempvalue==10**7:
        print(-1)
        exit()
    if value!=tempvalue:
        value=tempvalue
        kagilst.append(tempkagi)
print(value)

Submission status: Wrong Answer

Solution code:
from bisect import *
N,M=map(int,input().split())
kagi=[]
for i in range(M):
    a,b=map(int,input().split())
    C=list(map(int,input().split()))
    for i in range(b):
        C[i]-=1
    kagi.append([a,set(C)])

value=10**7
idx=-1
for i in range(M):
    if 0 in kagi[i][1] and kagi[i][0]<value:
        value=kagi[i][0]
        idx=i
if idx==-1:
    print(-1)
    exit()
kagilst=[idx]

takara=[set() for i in range(N)]
for m in range(M):
    for k in kagi[m][1]:
        takara[k].add(m)

for n in range(1,N):
    if [k for k in kagilst if n in kagi[k][1]]:
        continue
    tempvalue=10**7
    for i in range(len(kagilst)**2):

        for k in takara[n]:
            lst=[0 for x in range(n)]
            for z in kagilst+[k]:
                for m in kagi[z][1]:
                    if m<len(lst):
                        lst[m]=1
            A=bin(i)[2:]
            A=list(reversed(list(A)))
            for i in range(len(kagilst)-len(A)):
                A.append("0")
            for a in range(len(kagilst)):
                if A[a]=="1":
                    for h in kagi[kagilst[a]][1]:
                        if h<len(lst):
                            lst[h]=1
            if not 0 in lst:
                temptempvalue=value+sum([kagi[a][0] for a in range(len(kagilst)) if A[a]=="1"])+kagi[k][0]
                if temptempvalue<tempvalue:
                    tempvalue=temptempvalue
                    tempkagi=k

    if tempvalue==10**7:
        print(-1)
        exit()
    value=tempvalue
    kagilst.append(k)
print(value)

Submission status: Wrong Answer

Solution code:
from bisect import *
N,M=map(int,input().split())
kagi=[]
for i in range(M):
    a,b=map(int,input().split())
    C=list(map(int,input().split()))
    for i in range(b):
        C[i]-=1
    kagi.append([a,set(C)])

value=10**7
idx=-1
for i in range(M):
    if 0 in kagi[i][1] and kagi[i][0]<value:
        value=kagi[i][0]
        idx=i
if idx==-1:
    print(-1)
    exit()
kagilst=[idx]

takara=[set() for i in range(N)]
for m in range(M):
    for k in kagi[m][1]:
        takara[k].add(m)
exit()
for n in range(1,N):
    if [k for k in kagilst if n in kagi[k][1]]:
        continue
    tempvalue=10**7
    for k in takara[n]:
        lst=[0 for i in range(n)]
        for z in kagilst+[k]:
            for m in kagi[z][1]:
                if m<len(lst):
                    lst[m]=1
        for i in range(len(kagilst)**2):
            A=bin(i)[:2]
            A=list(reversed(list(A)))
            for a in range(len(kagilst)):
                if A[a]=="1":
                    for h in kagi[kagilst[a]][1]:
                        lst[h]=1
            if not 0 in lst:
                temptempvalue=value+sum([kagi[a][0] for a in range(len(kagilst)) if A[a]=="1"])+kagi[k][0]
                if temptempvalue<tempvalue:
                    tempvalue=temptempvalue
                    tempkagi=k
    if tempvalue==10**7:
        print(-1)
        exit()
    value=tempvalue
    kagilst.append(k)
print(value)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[0]*M
import heapq
import collections
from itertools import permutations
table=collections.defaultdict(list)
AC=[[0,set()] for i in range(M)]
C=[set() for i in range(M)]
for i in range(M):
  a,b=map(int,input().split())
  AC[i][0]=a
  AC[i][1]=set(map(int,input().split()))
dp=[10**9]*(2**N)
dp[0]=0

for i in range(1,2**N):
  k=0
  s=set()
  for j in range(N):
    if (i>>j)%2==1:
      dp[i]=min(dp[1<<j]+dp[i - (1<<j)],dp[i])
      s.add(j+1)
  #if i == 3:
    #print(dp[i])
  for a,c in AC:
    if c&s == s:
      dp[i]=min(dp[i],a)
  #print(dp[i],bin(i))
if dp[-1]==10**9:
  print(-1)
else:
  print(dp[-1])
#print(dp)

  
  
#print(AC)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[0]*M
import heapq
import collections
from itertools import permutations
table=collections.defaultdict(list)
AC=[[0,set()] for i in range(M)]
C=[set() for i in range(M)]
for i in range(M):
  a,b=map(int,input().split())
  AC[i][0]=a
  AC[i][1]=set(map(int,input().split()))
dp=[10**9]*(2**N)
dp[0]=0

for i in range(1,2**N):
  k=0
  s=set()
  for j in range(N):
    if (i>>j)%2==1:
      dp[i]=min(dp[1<<j]+dp[i - (1<<j)],dp[i])
      s.add(j+1)
  #if i == 3:
    #print(dp[i])
  for a,c in AC:
    if c&s == s:
      dp[i]=min(dp[i],a)
  #print(dp[i],bin(i))
print(dp[-1])
#print(dp)

  
  
#print(AC)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
import heapq
AC=[]
for i in range(M):
  a,b=map(int,input().split())
  #AC[i][0]=a
  tmp=set(map(int,input().split()))
  heapq.heappush(AC,(a,tmp))
g=set()
ans=0
while(AC):
  if len(g)==N:
    break
  a,c=heapq.heappop(AC)
  if c - g:
    ans+=a
    g|=c
  else:
    continue
if len(g)<N:
  print(-1)
else:
  print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) + list(map(int,input().split())) for _ in range(M)]
    ABC.sort(key = itemgetter(0))

    box = [False]*N
    ans = 0
    for abc in ABC:
        a,b = abc[:2]
        for c in abc[2:]:
            if not(box[c-1]):
                box[c - 1] = True
                ans += a
                break
        for c in abc[2:]:
            box[c-1] = True
    print(ans if box == [True]*N else -1)
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

l = []
ans = 0
for _ in range(M):
    a, b = map(int ,input().split())
    c = set(map(int ,input().split()))
    l.append([a/b, a, c])
l.sort(reverse=True)

selected = set()
inf = 10**8
while l and len(selected)!=N:
    perf, cost, treasures = l.pop()
    selected|=treasures
    ans += cost
    l = [i for i in l if i[2]&treasures!=i[2]]
    l.sort(reverse=True)

print(ans if selected == set(range(1, N+1)) else -1)

Submission status: Wrong Answer

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

l = []
ans = 0
for _ in range(M):
    a, b = map(int ,input().split())
    *c, = map(int ,input().split())
    l.append([a/b, a, c])
l.sort(reverse=True)

selected = set()
inf = 10**8
while l and len(selected)!=N:
    perf, cost, treasures = l.pop()
    if perf==inf:continue
    selected|=set(treasures)
    ans += cost
    
    size = len(l)
    for i in range(size):
        b = set(l[i][2])
        a = set(treasures)

        if a&b == b:
            l[i][0] = inf
            l[i][1] = 0
    l.sort(reverse=True)

print(ans if selected == set(range(1, N+1)) else -1)

Submission status: Wrong Answer

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

l = []
ans = 0
for _ in range(M):
    a, b = map(int ,input().split())
    *c, = map(int ,input().split())
    l.append([a/b, a, c])
l.sort(reverse=True)

selected = set()
while l and len(selected)!=N:
    perf, cost, treasures = l.pop()
    selected|=set(treasures)
    ans += cost
    
    size = len(l)
    for i in range(size):
        b = set(l[i][2])
        a = set(treasures)

        if a&b == b:
            l[i][0] = 10**8
            l[i][1] = 0
    l.sort(reverse=True)

print(ans if selected == set(range(1, N+1)) else -1)

Submission status: Wrong Answer

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

l = []
ans = 0
for _ in range(M):
    a, b = map(int ,input().split())
    *c, = map(int ,input().split())
    l.append([a/b, a, c])
l.sort(reverse=True)

selected = set()
while l and len(selected)!=N:
    perf, cost, treasures = l.pop()
    selected|=set(treasures)
    if not treasures:continue
    ans += cost
    
    size = len(l)
    for i in range(size):
        for t in treasures:            
            if t in l[i][2]:
                l[i][2].remove(t)
        if l[i][2]:
            l[i][0] = l[i][1]/len(l[i][2])
        else:
            l[i][0] = 10**8
            l[i][1] = 0
    l.sort(reverse=True)

print(ans if selected == set(range(1, N+1)) else -1)

Submission status: Wrong Answer

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

l = []
ans = 0
for _ in range(M):
    a, b = map(int ,input().split())
    *c, = map(int ,input().split())
    l.append([a/b, a, c])
l.sort(reverse=True)

selected = set()
while l and len(selected)!=N:
    perf, cost, treasures = l.pop()
    selected|=set(treasures)
    if not treasures:continue
    ans += cost
    
    size = len(l)
    for i in range(size):
        for t in treasures:            
            if t in l[i][2]:
                l[i][2].remove(t)
        l[i][0] = l[i][1]/len(l[i][2]) if l[i][2] else 10**8
    l.sort(reverse=True)

print(ans if selected == set(range(1, N+1)) else -1)

Submission status: Wrong Answer

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

ans = float('INF')
flag = False
opened = 2**n-1
for i in range(2**n):
    cost = 0
    box = 0
    for j in range(m):
        if i & 1<<j:
            cost += key[j][0]
            box |= key[j][1]
    if cost < ans and box == opened:
        flag = True
        ans = cost

print(ans if flag else -1)

Submission status: Wrong Answer

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

# define info dic
info_dic = {}
for i in range(m):
    a,b = map(int, input().split())
    c_list = list(map(int, input().split()))
    info_dic[a] = c_list

# make dp table
dp = {}
child_dp = {}
child_dp[0] = []
dp[0] = child_dp

# make dp table
for i in range(1, n+1):
    
    # init cadinate
    init_cost = float("inf")
    init_keys = []
    
    # check all keys 
    needed_keys = [i for i in range(1, i+1)]

    # search before table
    for min_i in range(0, i):

        # get before info
        before_cost = list(dp[min_i].keys())[0]
        before_keys = list(dp[min_i].values())[0]

        # もし, すでにi番目を開ける鍵を持っていれば
        if i in before_keys:
            init_cost = before_cost
            init_keys = before_keys


        else:
            # 1つの鍵について考える
            for cad_cost, cad_keys in info_dic.items():

                # 最良のカギなら
                if list(set(needed_keys) & (set(cad_keys) | set(before_keys))) == needed_keys and cad_cost + before_cost < init_cost:
                    init_cost = cad_cost + before_cost
                    init_keys = list(set(cad_keys) | set(before_keys))
        
    child_dp = {}
    child_dp[init_cost] = init_keys
    dp[i] = child_dp

if list(dp[n].keys())[0] == float("inf"):
    print(-1)
    exit()

print(list(dp[n].keys())[0])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [None] * M
K = [None] * M
for i in range(M):
    a, b = map(int, input().split())
    C = map(int, input().split())
    A[i] = a
    K[i] = sum([2 ** (i - 1) for i in C])


INF = (1 << 32) - 1
dp = [[INF] * (2 ** N) for _ in range(M + 1)]
for i in range(M + 1):
    dp[i][0] = 0

for i in range(M):
    k = K[i]
    a = A[i]
    for j in range(2 ** N):
        dp[i + 1][j | k] = min(dp[i + 1][j | k], dp[i][j | k], dp[i][j - k] + A[i])
        continue

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

Submission status: Wrong Answer

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

def main():
    N,M = map(int,input().split())
    INF = 10**7
    k = []
    for _ in range(M):
        a,b = map(int,input().split())
        c = list(map(int,input().split()))
        bit = 0
        for i in c:
            bit += 2**(i-1)
        k.append((a,bit))
    dp = np.full((1<<N),INF)
    dp[0] = 0
    for i in range(M):
        a,bit = k[i]
        for j in range(1<<N):
            af = bit|j
            dp[af] = min(dp[af],dp[j]+a)
            
    print(dp[-1] if dp[-1] != INF else -1)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

INF = 10 ** 15
dp = [INF for _ in range(2 ** N)]# dp[開閉のbit] = min(コスト)
dp[0] = 0

for i in range(M):
  for j in range(2 ** N - 1, -1, -1):
    if dp[j] != INF:
      dp[j | C[i]] = min(dp[j | C[i]], dp[j] + A[i])
      
print(dp[-1])

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
A=[0]*M
import collections
table=collections.defaultdict(list)
C=[set() for i in range(M)]
for i in range(M):
  a,b=map(int,input().split())
  A[i]=a
  c=list(map(int,input().split()))
  C[i]=set(c)
  for x in c:
    table[x].append((a,i))

opened=set()
used=set()
for i in range(1,N+1):
  if used & C[i-1]:
    opened.add(i)
    continue
  if len(table[i])==0:
    print(-1)
    exit(0)
  table[i].sort(key=lambda x:x[0])
  used.add(table[i][0][1])
  opened.add(i)
ans=0
for x in used:
  ans+=A[x]
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
key = []
key_i = []
for i in range(M):
  key.append(list(map(int, input().split())))
  key_i.append(list(map(int, input().split())))
keybin = [0]*M
for j in range(M):
  for x in key_i[j]:
    keybin[j] += 2**(x-1)
INF = float("inf")
DP = [[INF] * (2**N) for _ in range(M+1)]

DP[0][0] = 0
for i in range(1,M+1):
  for j in range(2**N):
    x = keybin[i-1]
    DP[i][j] = min(DP[i][j],DP[i-1][j])
    DP[i][j|x] = min(DP[i][j|x],DP[i-1][j|x], DP[i-1][j]+key[i-1][0])
print(DP[-1][-1])

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
dp = [INF]*(2**n)
dp[0] = 0
for i in range(m):
    val,b = inpl()
    c = inpl()
    key = 0
    for j in c:
        key += 2**(j-1)
    for _ in range(n**2):
        dp[_|key] = min(dp[_|key], dp[_]+val)
        
res = dp[-1]
print(res if res != INF else -1)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
key_prize = []
key_type = []
ans = 0
for i in range(M):
  key_prize.append([i for i in map(int,input().split())][0])
  ans += key_prize[i]
  key_type.append([i-1 for i in map(int,input().split())])

key_dict = {}
for i in range(M):
  key_dict[key_prize[i]] = key_type[i]

slist = sorted(key_dict.items(), key=lambda x: x[0], reverse=True)
i = 0
treasures = set(list(range(N)))
# 判定
keys = set()
for j in range(len(slist)):
  for k in range(len(slist[j][1])):
    keys.add(slist[j][1][k])
if keys != treasures:
  print("-1")
else:
  while i < len(slist):
    keys = set()
    for j in range(len(slist)):
      if i == j: continue
      for k in range(len(slist[j][1])):
        keys.add(slist[j][1][k])
    if keys == treasures:
      ans -= slist[i][0]
      slist.pop(i)
    else:
      i += 1
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations
def input():
	return sys.stdin.readline()[:-1]
n, m = map(int, input().split())
keys = []
for _ in range(m):
	a, b = map(int, input().split())
	c = list(map(int, input().split()))
	keys.append([a, sum([1<<(x-1) for x in c])])
dp = [10**30 for _ in range(1<<n)]
dp[0] = 0

for c, v in keys:
	dp[v] = dp[0]+c

for j in range(1, (1<<n)):
	for c, v in keys:
		dp[j|v] = min(dp[j|v], dp[j]+c)

if dp[(1<<n)-1] > 10**20:
	print(-1)
else:
	print(dp[(1<<n)-1])

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations
n, m = map(int, input().split())
keys = []
for _ in range(m):
	a, b = map(int, input().split())
	c = list(map(int, input().split()))
	keys.append([a, sum([1<<(x-1) for x in c])])
dp = [10**30 for _ in range(1<<n)]
dp[0] = 0

for c, v in keys:
	dp[v] = dp[0]+c

for i in range(1, n):
	for p in combinations(range(n), i):
		j = 0
		for q in p:
			j += (1<<q)
		for c, v in keys:
			dp[j|v] = min(dp[j|v], dp[j]+c)

if dp[(1<<n)-1] > 10**20:
	print(-1)
else:
	print(dp[(1<<n)-1])

Submission status: Wrong Answer

Solution code:
import sys
from itertools import combinations
def input():
	return sys.stdin.readline()[:-1]
n, m = map(int, input().split())
keys = []
for _ in range(m):
	a, b = map(int, input().split())
	c = list(map(int, input().split()))
	keys.append([a, sum([1<<(x-1) for x in c])])
dp = [10**30 for _ in range(1<<n)]
dp[0] = 0

for c, v in keys:
	dp[v] = dp[0]+c

for i in range(n-1, 0, -1):
	for p in combinations(range(n), i):
		j = 0
		for q in p:
			j += (1<<q)
		#print(j)
		for c, v in keys:
			dp[j|v] = min(dp[j|v], dp[j]+c)

if dp[(1<<n)-1] > 10**20:
	print(-1)
else:
	print(dp[(1<<n)-1])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
INF = 1001001001
key = []

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

dp = [INF] * (1<<N)
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = s | key[i][0]
        cost = dp[s] + key[i][1]
        dp[t] = min(dp[t], cost)
ans = dp[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
INF = 1001001001
key = []

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

dp = [INF] * (1<<N)
dp[0] = 0
for s in range(1<<N):
    for i in range(M):
        t = s | key[i][0]
        cost = dp[s] + key[i][1]
        dp[t] = min(dp[t], cost)
ans = dp[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N, M = map(int, input().split())
keys = {}
for _ in range(M):
    cost, n = map(int, input().split())
    key_set = 0
    for i in map(int, input().split()):
        key_set |= (1 << (i -1))
    keys[cost] = key_set

allstate = (1 << N) - 1
dp = collections.defaultdict(lambda:float('inf'))
dp[0] = 0

for cost, key_set in keys.items():
    ndp = collections.defaultdict(lambda:float('inf'))
    for state, val in dp.items():
        ndp[state] = min(ndp[state], val)
        ndp[state|key_set] = min(ndp[state|key_set], val + cost)
    dp = ndp

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

Submission status: Wrong Answer

Solution code:
import collections
N, M = map(int, input().split())
keys = {}
for _ in range(M):
    cost, n = map(int, input().split())
    key_set = 0
    for i in map(int, input().split()):
        key_set |= (1 << (i -1))
    keys[cost] = key_set

allstate = (1 << N) - 1
dp = collections.defaultdict(lambda:float('inf'))
dp[0] = 0

for cost, key_set in keys.items():
    ndp = collections.defaultdict(lambda:float('inf'))
    for state, val in dp.items():
        ndp[state] = min(ndp[state], val)
        ndp[state|key_set] = min(ndp[state|key_set], val + cost)
    dp = ndp

if allstate in dp:
    print(dp[allstate])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import collections
N, M = map(int, input().split())
keys = {}
for _ in range(M):
    cost, n = map(int, input().split())
    key_set = 0
    for i in map(int, input().split()):
        key_set |= 1 << i -1
    keys[cost] = key_set

allstate = (1 << N) - 1
dp = [float('inf')] * (1<<N)
dp[0] = 0

for cost, key_set in keys.items():
    for state in range(1<<N):
        if dp[state] == float('inf'): continue
        nstate = state | key_set
        dp[nstate] = min(dp[nstate], dp[state] + cost)

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

Submission status: Wrong Answer

Solution code:
import collections
N, M = map(int, input().split())
keys = {}
for _ in range(M):
    cost, n = map(int, input().split())
    key_set = 0
    for i in map(int, input().split()):
        key_set |= 1 << i -1
    keys[cost] = key_set

allstate = (1 << N) - 1
dp = collections.defaultdict(lambda:float('inf'))
dp[0] = 0

for cost, key_set in keys.items():
    ndp = dp.copy()
    for state, val in dp.items():
        ndp[state|key_set] = min(ndp[state|key_set], val + cost)
    dp = ndp
if allstate in dp:
    print(dp[allstate])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import collections
N, M = map(int, input().split())
keys = {}
for _ in range(M):
    cost, n = map(int, input().split())
    key_set = 0
    for i in map(int, input().split()):
        key_set |= 1 << i -1
    keys[cost] = key_set

allstate = (1 << N) - 1
dp = collections.defaultdict(lambda:float('inf'))
dp[0] = 0

for cost, key_set in keys.items():
    ndp = dp.copy()
    for state, val in dp.items():
        ndp[state|key_set] = min(ndp[state|key_set], val + cost)
    ndp[key_set] = min(ndp[key_set], cost)
    dp = ndp
if allstate in dp:
    print(dp[allstate])
else:
    print(-1)

Submission status: Wrong Answer

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

for i in range(m):
    a, b = list(map(int, input().split()))
    c = list(map(int, input().split()))
    keys.append([a] + c)
inf = 10 ** 11
dp = [[inf for i in range(2**n)] for j in range(m+1)]
for i in range(m):
    dp[i][0] = 0
for i in range(1,m+1):
    key_value = keys[i-1][0]
    can_open = keys[i-1][1:]
    for j in range(n ** 2):
        #print("{} => {}".format(can_open, trans(can_open)))
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        next = j | trans(can_open)
        dp[i][next] = min(dp[i][next], dp[i-1][j] + key_value)
#for i in range(m+1):
#    print(dp[i])
if dp[-1][-1] >= inf:
    print(-1)
else:
    print(dp[-1][-1])
"""
4 7
67786 3
1 3 4 
3497 1
2     
44908 3
2 3 4 
21560 3
2 3 4 
26230 1
2     
86918 1
3     
2900 3
1 2
"""

Submission status: Wrong Answer

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

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

3497 1
2     => 2

44908 3
2 3 4 => 14

2156 3
2 3 4 => 14

26230 1
2     => 2

86918 1
3     => 4
"""

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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


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


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

import numpy as np
N, M = map(int, raw_input().split())
a = []
b = []
c = []
for i in xrange(M):
    a_, b_ = map(int, raw_input().split())
    a.append(a_)
    b.append(b_)
    c.append(map(int, raw_input().split()))

# C ID of locker status
C = np.zeros(M, dtype = int)
for i in xrange(M):
    for j in xrange(b[i]):
        C[i] |= (1 << (c[i][j]-1))

# f[i][j]: Min money to achieve status j with 0~i keys
# f[i][j] = min{ f[i-1][C], f[i-1][j'] + a[i] }, j = j'|C[i]
# Initial: f
f = np.full([M, 2**N], -1, dtype=int)
f[0][C[0]] = a[0]
for i in xrange(1, M):
    for j in xrange(2**N):
        List = []
        if f[i-1][j] != -1:
            List.append(f[i-1][j])
        for k in xrange(2**N):
            if (f[i-1][k] != -1) and (k | C[i]) == j:
                List.append(f[i-1][k] + a[i])
        if List != []:
            f[i][j] = min(List)

res = f[M-1][2**N-1]
print res