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:
import fractions
INF = 10000000000

from collections import defaultdict, namedtuple
Arc = namedtuple('Arc', ('tail', 'weight', 'head'))

def spanning_arborescence(arcs, sink, kick):
    l=len(arcs)
    while l>=0:
        x=arcs[l-1]                                          #best incoming edges list traversed in the reverse order in which they were added
        l=l-1
        if x in kick:
           for arc in arcs:
               if arc==kick[x] or arc in kick[x]:
                   i=arcs.index(arc)                  #every edge will kick out one edge inside the merged node, breaking the cycle.
                   arcs[i]=x                          #every edge in the Kick dictionary is removed from the best incoming edge(arcs) list
                          
    return(set(arcs))

def find_cycle(successor, sink):
        visited = {sink}
        for node in successor:
            cycle = []
            while node not in visited:
                visited.add(node)           #keeping a track of the traversed nodes
                cycle.append(node)                                                               
                node = successor[node]      #if the node's parent is present in the list 'cycle',it verifies the presence of a cycle 
            if node in cycle:
                return cycle[cycle.index(node):]
        return None

class MSTT:
    def max_spanning_arborescence(self,arcs, sink): 
        kick={}                                              #dictionary storing the kicked out edges of the arcs
        good_arcs = []                                       #list storing the best (maximum) arc of every node
        quotient_map = {arc.tail: arc.tail for arc in arcs}   #dictionary for tail(key) to tail(value) mapping of every arc
        quotient_map[sink] = sink
        score={arc:arc.weight for arc in arcs}      #score for updating the weights on detecting a cycle 
        while True:
            max_arc_by_tail_rep = {}    #dictionary storing the maximum incoming arc(value) of every node(key)                                                                             
            successor_rep = {}          #dictionary storing the parent node of every node selected in max_arc_by_tail_rep                                                                       
            for arc in arcs:
                if arc.tail == sink:    #avoiding the arcs which have root as their tail
                    continue
                tail_rep = quotient_map[arc.tail]
                head_rep = quotient_map[arc.head]
                if tail_rep == head_rep:                 #avoiding the self loops 
                    continue
                if tail_rep not in max_arc_by_tail_rep or score[max_arc_by_tail_rep[tail_rep]] < score[arc]:    
                    max_arc_by_tail_rep[tail_rep] = arc         #selecting the maximum incoming arc for every node                                                       
                    successor_rep[tail_rep] = head_rep
            
            cycle_reps = find_cycle(successor_rep, sink)            
            if cycle_reps is None:                                 #Repeated until every non-root node has an incoming edge and no cycles are formed                    
                 z=[]                                               
                 z.extend(max_arc_by_tail_rep.values())             
                 while z:
                     y=z.pop(0)
                     good_arcs.append(y) if y not in good_arcs else None         
                 return spanning_arborescence(good_arcs, sink,kick)
            for arc in arcs:
                tail_rep = quotient_map[arc.tail]
                head_rep = quotient_map[arc.head]
                if arc.tail == sink:
                    continue
                if tail_rep == head_rep:
                    continue
                if tail_rep in cycle_reps and arc!= max_arc_by_tail_rep[tail_rep] and head_rep not in cycle_reps:
                    score[arc]=score[arc]-score[max_arc_by_tail_rep[tail_rep]]                                      #updating the score of the incoming edges whose tails form a cycle
                    y=kick.get(arc)
                    if y is not None:
                        kick.setdefault(arc,[]).append(max_arc_by_tail_rep[tail_rep])                               #adding the best incoming arc as the kicked out edges of every incoming arc whose score was updated
                    else:
                        kick.setdefault(arc,[]).append(max_arc_by_tail_rep[tail_rep])
            z=[]
            z.extend(max_arc_by_tail_rep.values())
            while z:
                y=z.pop(0)
                good_arcs.append(y) if y not in good_arcs else None                                                 #Adding the best incoming arc of every merged and unmerged nodes of the graph
            cycle_rep_set = set(cycle_reps)
            cycle_rep = cycle_rep_set.pop()
            quotient_map = {node: cycle_rep if node_rep in cycle_rep_set else node_rep for node, node_rep in quotient_map.items()}    #contracting the nodes in cycle_reps
            
    def min_spanning_arborescence(self,arcs, sink): 
        kick={}                                              #dictionary storing the kicked out edges of the arcs
        good_arcs = []                                       #list storing the best (minimum) arc of every node
        quotient_map = {arc.tail: arc.tail for arc in arcs}   #dictionary for tail(key) to tail(value) mapping of every arc
        quotient_map[sink] = sink
        score={arc:arc.weight for arc in arcs}      #score for updating the weights on detecting a cycle 
        while True:
            min_arc_by_tail_rep = {}    #dictionary storing the minimum incoming arc(value) of every node(key)                                                                             
            successor_rep = {}          #dictionary storing the parent node of every node selected in max_arc_by_tail_rep                                                                       
            for arc in arcs:
                if arc.tail == sink:    #avoiding the arcs which have root as their tail
                    continue
                tail_rep = quotient_map[arc.tail]
                head_rep = quotient_map[arc.head]
                if tail_rep == head_rep:                 #avoiding the self loops 
                    continue
                if tail_rep not in min_arc_by_tail_rep or score[min_arc_by_tail_rep[tail_rep]] > score[arc]:    
                    min_arc_by_tail_rep[tail_rep] = arc         #selecting the maximum incoming arc for every node                                                       
                    successor_rep[tail_rep] = head_rep
            
            cycle_reps = find_cycle(successor_rep, sink)            
            if cycle_reps is None:                                 #Repeated until every non-root node has an incoming edge and no cycles are formed                    
                 z=[]                                               
                 z.extend(min_arc_by_tail_rep.values())             
                 while z:
                     y=z.pop(0)
                     good_arcs.append(y) if y not in good_arcs else None         
                 return spanning_arborescence(good_arcs, sink,kick)
            for arc in arcs:
                tail_rep = quotient_map[arc.tail]
                head_rep = quotient_map[arc.head]
                if arc.tail == sink:
                    continue
                if tail_rep == head_rep:
                    continue
                if tail_rep in cycle_reps and arc!= min_arc_by_tail_rep[tail_rep] and head_rep not in cycle_reps:
                    score[arc]=score[arc]-score[min_arc_by_tail_rep[tail_rep]]                                      #updating the score of the incoming edges whose tails form a cycle
                    y=kick.get(arc)
                    if y is not None:
                        kick.setdefault(arc,[]).append(min_arc_by_tail_rep[tail_rep])                               #adding the best incoming arc as the kicked out edges of every incoming arc whose score was updated
                    else:
                        kick.setdefault(arc,[]).append(min_arc_by_tail_rep[tail_rep])
            z=[]
            z.extend(min_arc_by_tail_rep.values())
            while z:
                y=z.pop(0)
                good_arcs.append(y) if y not in good_arcs else None                                                 #Adding the best incoming arc of every merged and unmerged nodes of the graph
            cycle_rep_set = set(cycle_reps)
            cycle_rep = cycle_rep_set.pop()
            quotient_map = {node: cycle_rep if node_rep in cycle_rep_set else node_rep for node, node_rep in quotient_map.items()}    #contracting the nodes in cycle_reps

def read():
    N, M = map(int, input().strip().split())
    A = [0 for _ in range(M)]
    B = [0 for _ in range(M)]
    C = [list() for _ in range(M)]
    V = 1 + M + N
    graph = [[INF for _ in range(V)] for _ in range(V)]
    for i in range(1, M+1):
        a, b = map(int, input().strip().split())
        c = list(map(int, input().strip().split()))
        graph[0][i] = a
        for _c in c:
            graph[i][M+_c] = 0
    return N, M, graph, V

def prim(N, M, graph, V):
    min_cost = [INF for _ in range(V)]
    used = [False] * V
    min_cost[0] = 0
    res = 0
    while True:
        v = -1
        for u in range(V):
            if not used[u] and (v == -1 or min_cost[u] < min_cost[v]):
                v = u
        if v == -1:
            break
        used[v] = True
        res += min_cost[v]
        for u in range(V):
            min_cost[u] = min(min_cost[u], graph[v][u])
    return res if res < INF else -1
 

def solve(N, M, graph, V):
    m = MSTT()
    edges = []
    for i in range(V):
        for j in range(V):
            if graph[i][j] != INF:
                edges.append(Arc(tail=j, weight=graph[i][j], head=i))
    msa = m.min_spanning_arborescence(edges, 0)
    if len(msa) == V - 1:
        return sum([arc.weight for arc in msa])
    else:
        return -1

if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

Submission status: Wrong Answer

Solution code:
def view():
    global keyboxes
    for keybox in keyboxes:
        for key in keybox:
            print(key.value,key.cans)
        print()

class Key():
    def __init__(self,value,cans):
        self.value=value
        self.cans=cans
    
    def __eq__(self,other):
        return self.value==other.value
    
    def __lt__(self,other):
        return self.value<other.value
    
    def __gt__(self,other):
        return self.value>other.value
    
N,M=map(int,input().split())
keys=[]
for i in range(M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    cans=[False for i in range(N)] # 宝箱の番号は0-イニシャルで扱う
    for i in c:
        cans[i-1]=True
    keys.append(Key(a,cans))

keyboxes=[[] for i in range(N)]
for key in keys:
    for i in range(N):
        if key.cans[i]:
            keyboxes[i].append(key)
        
for keybox in keyboxes:
    keybox.sort()

ans=0
flag=True

ansbox=[]
for i in range(N):
    if keyboxes[i]==[]:
        flag=False
        break
    else:
        key=keyboxes[i][0]
        if key not in ansbox:
            ansbox.append(key)
            ans+=key.value

print(ans if flag else -1)

Submission status: Wrong Answer

Solution code:
import sys
N, M = [int(i) for i in input().split()]
A = []
B = []
C = []
K = [0 for i in range(N)]
ans = 0
for i in range(M):
    a, b = [int(i) for i in input().split()]
    c = [int(i) for i in input().split()]
    ans += a
    A.append([a, i])
    B.append(b)
    C.append(c)
    for ci in c:
        K[ci-1] += 1
if min(K) == 0:
    print(-1)
    sys.exit(0)
A.sort(reverse=True)
for i in range(M):
    for ci in C[A[i][1]]:
        if K[ci-1] - 1 == 0:
            break
    else:
        for ci in C[A[i][1]]:
            K[ci-1] -= 1
        ans -= A[i][0]
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split()) # Nは宝 Mは鍵
keys = []
for _ in range(0, M):
  cost, _ = map(int, input().split())
  treasure = map(int, input().split())
  keys.append({'cost': cost, 'treasure': list(treasure)})
keys = sorted(keys, lambda x: x['cost'])

opened_t = []
used_key = [] 

for key in keys:
  use_key = False
  for t in key['treasure']:
    if t not in opened_t:
      opened_t.append(t)
      use_key = True
  if use_key:
    used_key.append(key)
  if len(opened_t) == N:
    break
if len(opened_t) == N:
  cost = sum([k['cost'] for k in used_key])
  print(cost)    
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
AB = []
C = []
if N > M:
  print(-1)
  exit()
for i in range(M*2):
  if i % 2 == 0:
    ab = list(map(int,input().split()))
    AB.append(ab)
  else:
    c = list(map(int,input().split()))
    C.append(c)
cost = float("inf")
for i in range(M):
  for j in range(M):
    tmp = set()
    if len(C[i]) + len(C[j]) >= N:
      tmp |= set(C[i])
      tmp |= set(C[j])
      if len(tmp) == N:
        cost = min(cost,AB[i][0] + AB[j][0])
print(cost)

Submission status: Wrong Answer

Solution code:
from collections import Counter

def main():
    N, M = map(int, input().split())
    a = [None]*M
    b = [None]*M
    c = [None]*M
    for i in range(M):
        a[i], b[i] = map(int, input().split())
        c[i] = [int(i) for i in input().split()]

    flag = [False]*N
    c_list = [None]*N
    inf = 10**5 + 10
    minlist = [inf] * N
    for i in range(N):
        for j in range(M):
            if i+1 in c[j]:
                if a[j] < minlist[i]:
                    minlist[i] = a[j]
                    c_list[i] = j
    
    if inf in minlist:
        print("-1")
    else:
        m = Counter(minlist)
        print(sum(m.keys()))
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
A = [] #値段
B = [] #Cの個数
C = [] #開けられる宝箱
for i in range(M):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
    c = set(map(int,input().split()))
    C.append(c)

# 各宝箱を開ける最小費用
min_cost = [100001]*N
for i in range(N):
    for j in range(M):
        if i+1 in C[j]:
            if A[j] < min_cost[i]:
                min_cost[i] = A[j]
if 100001 in min_cost:
    print(-1)
    exit()
print(sum(set(min_cost)))

Submission status: Wrong Answer

Solution code:
a,b=map(int,input().split())
c=[[]for i in range(b)]
for i in range(b):
  x,y=map(int,input().split())
  c[i].append(x)
  z=list(map(int,input().split()))
  for j in z:
    c[i].append(j-1)
  
c=sorted(c)
ans=0
s=[-1 for i in range(a)]
for i in range(b):
  h=0
  for j in range(1,len(c[i])):
    if s[c[i][j]]==-1:
      for k in range(1,len(c[i])):
        s[c[i][k]]=i
      ans+=c[i][0]
      h=1
      break
  if h==1:
    continue
  d=0
  e=[]
  for j in range(1,len(c[i])):
    k=s[c[i][j]]
    if not (k in e):
      e.append(k)
      d+=c[k][0]
  for j in range(a):
    if (not (j in c[i])) and s[j] in e:
      break
    if j==a-1:
      if c[i][0]<d:
        for k in range(1,len(c[i])):
          s[c[i][k]]=i
          ans=ans-d+c[i][0]
          
for i in range(a):
  if s[i]==-1:
    print(-1)
    exit()
    
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def main():
	[n,m]=[int(x) for x in input().split()]
	data=[]
	for i in range(m):
		[p,num]=[int(x) for x in input().split()]
		data.append([p,])
		data[-1].append([int(x) for x in input().split()])
	#print(data)
	
	dd = defaultdict(int)
	all_index=sum([item[1] for item in data],[])
	for key in all_index:
		dd[key] += 1
	#print(dd)

	index_count=list(dd.items())
	index_count.sort(key=lambda x:x[1])
	
	ans=[]
	while index_count!=[]:
		#print(index_count)
		kouho=[item for item in data if index_count[0][0] in item[1]]
		if kouho==[]:
			print(-1)
			exit()
		kouho.sort(key=lambda x:x[0])
		ans.append(kouho[0])
		index_count=[item for item in index_count if item[0] not in kouho[0][1]]
	
	#print(ans)
	#print(set(sum([item[1] for item in ans],[])))
	#print(set(range(1,n+1)))
	if set(sum([item[1] for item in ans],[]))!=set(range(1,n+1)):
		print(-1)
	else:
		print(sum([item[0] for item in ans]))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

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

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

ans = float('inf')

def subset(cost, key, keyset, ans_temp):
    keyset2 = keyset.copy()
    keyset2 |= set(key[0])
    if len(keyset2) > len(keyset):
        ans_temp += cost[0]
        keyset = keyset2

    global ans
    if len(cost) == 1 and ans_temp != -1 and len(keyset) == n:
        ans = min(ans, ans_temp)
        return
    elif len(keyset) == n:
        ans = min(ans, ans_temp)
        return
    else:
        for i in range(1, len(cost)):
            subset(cost[i:], key[i:], keyset, ans_temp)


for i in range(m):
    ans_temp = -1
    key_temp = set()
    subset(cost, key, key_temp, 0)

    if ans_temp != -1 and len(key_temp) == n:
        ans = min(ans, ans_temp)

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

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
shop = []
c_list = []
ans = 0
from collections import defaultdict
cnt = defaultdict(int)
for i in range(M):
    a, b = map(int, input().split())
    ans += a
    shop.append((a, b, i))
    cc = list(map(int, input().split()))
    c_list.append(cc)
    for c in cc:
        cnt[c] += 1


items = sorted(shop, key=lambda x:-x[0])

for i in range(1, N+1):
    if cnt[i] == 0:
        print(-1)
        exit()
for a, b, i in items:
    cc = c_list[i]
    # print(a, b, i, cc)
    al = True
    for c in cc:
        if cnt[c] == 1:
            al =False
    if not al:
        #print("s")
        continue
    else:
        for c in cc:
            cnt[c] -= 1
        ans -= a
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=[int(j) for j in input().split()]
c=[]
a=[]
l=[[] for i in range(n+1)]
dp=[10**18]*(2**(n))
ll=[0]*(n+1)
for i in range(m):
    x,y=[int(j) for j in input().split()]
    a.append(x)
    tmp=set([int(j) for j in input().split()])
    for j in tmp:
        ll[j]=1
    ind=0
    for j in range(1,n+1):
        if j in tmp:
            ind+=2**(j-1)
    dp[ind]=x
if sum(ll)!=n:
    print(-1)
    exit()

for i in range(1,2**n):
    for j in range(i+1,2**n):
        dp[i|j]=min(dp[i|j],dp[i]+dp[j])

if dp[-1]!=10**18:
    print(dp[-1])
    print(dp)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from sys import stdin

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = []
B = []
C = []
for _ in range(M):
    ab = [int(x) for x in stdin.readline().rstrip().split()]
    A.append(ab[0])
    B.append(ab[1])
    C.append([int(x) for x in stdin.readline().rstrip().split()])

opened = [False] * N
keys = [False] * M


def dfs(op, c, k):
    if False not in op:
        return c
    if False not in keys:
        return 10 ** 7
    output = 10 ** 7
    for n in range(M):
        if not k[n]:
            kk = k
            kk[n] = True
            opp = op
            for x in C[n]:
                opp[x - 1] = True
            output = min(output, dfs(opp, c + A[n], kk))
    return output


ans = dfs(opened, 0, keys)
if ans == 10 ** 7:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
box = [100001]*n
samp = [100001]*n
number = [0]*n
value = 0
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    for j in range(b):
        samp[c[j]-1] = a
    for k in range(n):
        box[k] = min(box[k],samp[k])
        if box[k]<samp[k]:
            number[k]=i
if 100001 in box:
    print(-1)
else:
    for i in range(n):
        if box.count(box[i])>=2 and number[i:n].count(number[i])==1:
            value += box[i]
        elif box.count(box[i])==1:
            value += box[i]
    print(sum(set(box)))

Submission status: Wrong Answer

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

for _ in range(m):
    l2 = [int(i)for i in input().split()]+[[int(i)-1 for i in input().split()]]
    l.append([l2[0]/l2[1]]+l2)


l2 = [0 for i in range(n)]
for i in l:
    for j in i[3]:
        l2[j]=1
if 0 in l2:
    print(-1)
    exit()

l.sort(key=lambda x:x[0])
l.reverse()
l2 = [0 for i in range(n)]
    
for i in range(m):
    for j in l[i][3]:
        l2[j] = i+1
cnt = 0
for i in list(set(l2)):
    cnt += l[i-1][1]
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
n,m=map(int,input().split())
keys=[]
boxes=[0]*n
allsum=0
for i in range(m):
  a,b=map(int,input().split())
  targets=list(map(int,input().split()))
  allsum=allsum+a
  for j in range(len(targets)):
    targets[j]=targets[j]-1
    boxes[targets[j]]=boxes[targets[j]]+1
  keys.append([a,targets])

if 0 in boxes:
  print(-1)
else:
  newkeys=sorted(keys, key=lambda x: (x[0],len(x[1])),reverse=True)
  for i in range(len(newkeys)):
    tar=newkeys[i][1]
    ng=False
    for j in range(len(tar)):
      if boxes[tar[j]]<2:
        ng=True
        break
    if ng!=True:
      allsum=allsum-newkeys[i][0]
      for p in range(len(tar)):
        boxes[tar[p]]=boxes[tar[p]]-1
  print(allsum)

Submission status: Wrong Answer

Solution code:
import numpy as np
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

inf = 100000000
dp = np.full([2]*n, inf)
dp[tuple([0]*n)] = 0

for i in range(m):
    a = d[2*i][0]
    b = d[2*i][1]
    c = d[2*i+1]
    
    for x in c:
        l0 = [0]*n
        l1 = [1]*n
        l0[x-1] = slice(None)
        l1[x-1] = slice(None)
        dp[tuple(l1)] = np.minimum(dp[tuple(l0)] + a, dp[tuple(l1)])
    
ans = dp[tuple([1]*n)]
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import itertools

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

INF = 999999999999999999999999

n,m = get_nums_l()

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

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

    #print(cost,b)


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

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

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

def solve(targets):
    
    #print(targets)

    if len(targets) == 0:
        return 0

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

    all_s = set(targets)

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

    _min = keys[keyn]

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

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

Submission status: Wrong Answer

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

# print(ab, C)
ab.sort()
# print(ab)

cost = 0
bag = [False] * (n+1)
for i in range(m):
    a = 0
    for j in ab[i][2]:
        if bag[j] == False:
            bag[j] = True
            a += 1
            if a == 1:
                cost += ab[i][0]
    tmp = [False] * (n+1)
    for j in ab[i][2]:
        tmp[j] = True
        if bag == tmp:
            if cost > ab[i][0]:
                cost = ab[i][0]
                bag = tmp

cnt = 0
for i in range(n+1):
    if bag[i] == True:
        cnt += 1

if cnt == n:
    print(cost)
else:
    print(-1)

# 4 3
# 100 2
# 1 2
# 2000 3
# 2 3 4
# 2050 4
# 1 2 3 4

Submission status: Wrong Answer

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

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

A = []

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

A.sort()

ans = [-1] * N

total = 0

for a in A:
    cost = a[0]
    kind = a[1]
    first = True
    for k in kind:
        if ans[k-1] == -1:
            ans[k-1] = 1
            if first:
                total += cost
                first = False

if ans.count(-1) > 0:
    print(-1)
    sys.exit(0)

print(total)

Submission status: Wrong Answer

Solution code:
import numpy as np
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

inf = 100000000
dp = np.full([2]*n, inf)
dp[tuple([0]*n)] = 0

for i in range(m):
    a = d[2*i][0]
    b = d[2*i][1]
    c = d[2*i+1]
    
    l0 = [0]*n
    l1 = [1]*n
    for x in c:
        l0[x-1] = slice(None)
        l1[x-1] = slice(None)
        dp[tuple(l1)] = np.minimum(dp[tuple(l0)] + a, dp[tuple(l1)])
    
ans = dp[tuple([1]*n)]
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
takara = [0] * n
key = [0] * n

for i in range(m):
	a, b = map(int, input().split())
	c = list(map(int, input().split()))
	for j in range(b):
		ma = takara[c[j]-1]
		if ma == 0:
			takara[c[j]-1] = a
			key[c[j]-1] = i + 1
		else:
			if a < ma:
				takara[c[j]-1] = a
				key[c[j]-1] = i + 1

if 0 in takara:
	print("-1")
else:
	s = 0
	for i in range(len(set(key))):
		s += takara[i]
	print(s)

Submission status: Wrong Answer

Solution code:
import sys
import collections
import copy
sys.setrecursionlimit(4100000)

n,m = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for _ in range(m*2)]

dic = {}

for i in range(len(a)):
    if i%2 == 0:
        continue
    if dic.get(tuple(a[i])):
        dic[tuple(a[i])] = min(dic[tuple(a[i])], a[i-1][0])
    else:
        dic[tuple(a[i])] = a[i-1][0]
starts = collections.defaultdict(list)
for key in dic:
    starts[key[0]].append((key,dic[key]))

def dfs(ansd,ons, cur):
    # print(ons)
    if sum(ons) == 0:
        ansd[0] = min(ansd[0], cur)
        return
    for i in range(len(ons)):
        if ons[i] == 1:
            # print(starts[i],i)
            for child in starts[i+1]:
                dons = copy.deepcopy(ons)
                for z in child[0]:

                    # print(child[0])
                    dons[z-1] = 0
                dfs(ans,dons,cur+child[1])
            break


ans = [float('inf')]
dfs(ans,[1]*(n),0)

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

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
N,M = list(map(int, readline().split()))

q = 10**5 + 1
h = []
for i in range(M):
    a, b = list(map(int, readline().split()))
    c = list(map(int, readline().split()))
    bi = ['0'] * N
    for cc in c:
        bi[cc-1] = '1'
    d = int(''.join(bi), 2)
    if bin(d) == '0b' + '1' * N:
        q = min(a, q)
    h.append([a,b,d])

h.sort(key=lambda x: x[0])
# print(h)

p = h[0][0]
bit = h[0][2]
for i in range(M-1):
    tmp = bit
    res = bit | h[i+1][2]
    # print(tmp,res)
    if tmp != res:
        bit = res
        p += h[i+1][0]

if bin(bit) == '0b' + '1' * N:
    print(min(p, q))
else:
    print('-1')

Submission status: Wrong Answer

Solution code:
import sys
import heapq

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    can_open = dict()
    key_count = dict()
    key = dict()
    for i in range(N): 
        key_count[i] = 0
        key[i] = set()

    q = []
    heapq.heapify(q)

    cost = 0
    for i in range(M):
        a, b = map(int, input().split())
        cost += a
        key[i] = set([int(k) - 1 for k in input().split()])
        qk = [-a/b, -a, b, i]
        heapq.heappush(q, qk)
        for k in key[i]: key_count[k] += 1

    for c in key_count:
        if key_count[c] == 0:
            print(-1)
            break
    else:
        while q:
            av, a, b, m = heapq.heappop(q)
            for k in key[m]:
                if key_count[k] == 1: break
            else:
                cost += a
                for k in key[m]: key_count[k] -= 1

        print(cost)

    return 0

if __name__ == "__main__":
    solve()