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: Runtime Error

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

class Key:
    def __init__(self, a, b, c):
        self.a = a
        self.b = b
        self.c = c

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

def solve(i, j):
    if dp[i][j] != inf:
        return dp[i][j]
    else:
        remain = j
        for c in keys[i].c:
            remain = remain & ~(1 << (c-1))

        if i > 0:
            dp[i][j] = min(solve(i-1, remain) + keys[i].a, solve(i-1, j))
        elif remain == 0:
            dp[i][j] = keys[i].a

        return dp[i][j]


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

ans = solve(m-1, 2**n-1)
if ans == inf:
    ans = -1
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

class Key:
    def __init__(self, a, b, c):
        self.a = a
        self.b = b
        self.c = c

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

def solve(i, j):
    if dp[i][j] != math.inf:
        return dp[i][j]
    else:
        remain = j
        for c in keys[i].c:
            remain = remain & ~(1 << (c-1))

        if i > 0:
            dp[i][j] = min(solve(i-1, remain) + keys[i].a, solve(i-1, j))
        elif remain == 0:
            dp[i][j] = keys[i].a

        return dp[i][j]


dp = [[math.inf] * (2**n)]*m
for i in range(m):
    dp[i][0] = 0

ans = solve(m-1, 2**n-1)
if ans == math.inf:
    ans = -1
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

class Key:
    def __init__(self, a, b, c):
        self.a = a
        self.b = b
        self.c = c

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

def solve(i, j):
    if dp[i][j] != math.inf:
        return dp[i][j]
    else:
        remain = j
        for c in keys[i].c:
            remain = remain & ~(1 << (c-1))

        if i > 0:
            dp[i][j] = min(solve(i-1, remain) + keys[i].a, solve(i-1, j))
        elif remain == 0:
            dp[i][j] = keys[i].a

        print(i, j, '->', dp[i][j])
        return dp[i][j]


dp = [[math.inf] * (2**n)]*m
for i in range(m):
    dp[i][0] = 0

ans = solve(m-1, 2**n-1)
if ans == math.inf:
    ans = -1
print(ans)

Submission status: Runtime Error

Solution code:
n,m= map(int,input().split())
a = [0]*m
b = [0]*m
c = []
d = [0]*m
gg = []

def kumi(st,bi,cb):
    for j in range(st+1,len(c)):
        if d[j] != 2**n-1:
            tmpbi = bi | d[j]
            if tmpbi == 2**n-1:
                g=0
                for z in cb+[j]:
                    g += a[z]
                gg.append(g)       
            elif tmpbi != bi:
                kumi(j,tmpbi,cb+[j])

dall = 0
for i in range(m):
    aa,bb = map(int,input().split())
    a[i]=aa
    b[i]=bb
    cc = list(map(int,input().split()))
    c.append(cc)
    for l in cc:
        d[i] |= 2**(n-l)
    dall |= d[i]

if (dall!=2**n-1):
    print('-1')
else:
    g = 999999999
    for i in range(m):
        if d[i]==2**n-1:
            g = min(g,a[i])
        else:
            kumi(i,d[i],[i])
   
if len(gg)>0:
    print(min(g,min(gg)))
else:
    print(g)

Submission status: Runtime Error

Solution code:
import numpy as np

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

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

print(dp[1 << n] if dp[1 << n] < float('inf') else -1)

Submission status: Runtime Error

Solution code:
boxes_n, keys_n = map(int,input().split())

dt = {}
for i in range(keys_n):
	cost, unlock = map(int, input().split())
	dt[(i, cost)] = list(map(int, input().split()))

items = list(dt.keys())
def find_min_cost(items, opened):
	if len(opened) == boxes_n:
		return 0
	elif len(items) == 0:
		return 100000000
	min_so_far = find_min_cost(items[1:],opened)
	o = opened.copy()
	for i in dt[items[0]]:
		o.add(i)
	other_min = items[0][1] + find_min_cost(items[1:], o)
	return min(min_so_far, other_min)

cost = find_min_cost(items, set())
if cost >= 100000000:
	print(-1)
else:
	print(cost)

Submission status: Runtime Error

Solution code:
boxes_n, keys_n = map(int,input().split())

dt = {}
for i in range(keys_n):
	cost, unlock = map(int, input().split())
	dt[(i, cost)] = list(map(int, input().split()))

items = list(dt.keys())
def find_min_cost(items, opened):
	if len(opened) == boxes_n:
		return 0
	elif len(items) == 0:
		return 100000000
	min_so_far = find_min_cost(items[1:],opened)
	o = opened.copy()
	for i in dt[items[0]]:
		o.add(i)
	other_min = items[0][1] + find_min_cost(items[1:], o)
	return min(min_so_far, other_min)

cost = find_min_cost(items, set(),[])
if cost >= 100000000:
	print(-1)
else:
	print(cost)

Submission status: Runtime Error

Solution code:
import itertools

n,m = map(int,input().split())
list_a = []
list_b = []
list_c = []
for i in range(m):
    tmp_a,tmp_b = map(int,input().split())
    tmp_c = input().split()
    tmp_c = [int(tmp_c[i]) for i in range(tmp_b)]
    list_a.append(tmp_a)
    list_b.append(tmp_b)
    list_c.append(tmp_c)

stuff = list(range(m))
money_list=[]
for L in range(1, len(stuff)):
    for subset in itertools.combinations(stuff, L):
        tmp_list = []
        for list_i in subset:
            tmp_list = tmp_list + list_c[list_i]
        # print(list(set(tmp_list)))
        if len(set(tmp_list)) == n:
            tmp_money = 0
            for list_i in subset:
                tmp_money = tmp_money + list_a[list_i]
            money_list.append(tmp_money)
          
print(min(money_list))

Submission status: Runtime Error

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

def main():
    N, M = map(int, input().split())
    abc = []
    for i in range(M):
        a, b = map(int, input().split())
        c = np.array(list(map(int, input().split()))) - 1
        abc.append((a, b, c))
    abc = sorted(abc)
    INF = int(1e10)
    dp = np.full(N, INF, dtype=int)

    ans = 0
    for i in range(M):
        # print(dp)
        a, b, c = abc[i]
        if any(dp[c] == INF):
            dp[c] = np.minimum(dp[c], a)
            ans += a

    ok = True
    for i in range(N):
        if dp[i] == INF:
            ok = False
            break
    
    if ok:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def main():
    N, M = map(int, input().split())
    abc = []
    for i in range(M):
        a, b = map(int, input().split())
        c = np.array(list(map(int, input().split()))) - 1
        abc.append((a, b, c))
    abc = sorted(abc)
    INF = int(1e10)
    dp = np.full(N, INF, dtype=int)

    ans = 0
    for i in range(M):
        print(dp)
        a, b, c = abc[i]
        if any(dp[c] == INF):
            dp[c] = np.minimum(dp[c], a)
            ans += a

    ok = True
    for i in range(N):
        if dp[i] == INF:
            ok = False
            break
    
    if ok:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys, copy
from collections import deque


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

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

Submission status: Runtime Error

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

def main():
    N, M = map(int, input().split())
    abc = []
    for i in range(M):
        a, b = map(int, input().split())
        c = np.array(list(map(int, input().split()))) - 1
        abc.append((a, b, c))
    abc = sorted(abc)
    INF = int(1e10)
    dp = np.full(N, INF, dtype=int)

    ans = 0
    for i in range(M):
        a, b, c = abc[i]
        now = sum(dp[c])
        if now >= INF:
            dp[c] = np.minimum(dp[c], a)
            ans += a

    ok = True
    for i in range(N):
        if dp[i] == INF:
            ok = False
            break
    
    if ok:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
def dfs(cost,S,L,N,T):#L,N,Tは定数
    mn=10**10
    if len(S)==N:
        return cost
    for i in T:
        if i in S:
            continue
        else:
            bad=[]
            safe_idx=0
            safe_cost=10**10
            for j,e in enumerate(L):
                if i in e[1] and len(S|e[1])-len(S)==1:
                        bad.append(j)
                        if e[0]<safe_cost:
                            safe_cost=e[0]
                            safe_idx=len(bad)-1
            if bad:
                bad[safe_idx]=None
            
            
            for j,e in enumerate(L):
                if j in bad:
                    continue
                if i in e[1]:
                    mn=min(mn,dfs(cost+e[0],(S|e[1]),L,N,T))

    return mn
                    


def main():
    full=set(list(range(1,13)))
    k=set()
    T=np.zeros(12)
    N,M=map(int,input().split())
    A=[]
    L=[]
    for i in range(M):
        a,_=map(int,sys.stdin.readline().split())
        C=set(map(int,sys.stdin.readline().split()))
        for c in C:
            T[c]+=1
            
        k=k.union(C)
        L.append((a,C))

    L.sort(key=lambda x:x[0])

    if len(k)<N:#全部の宝を開けるだけのカギがない
        return -1

    T=np.argsort(np.array(T))+1
    return dfs(0,set(),L,N,T)
    

print(main())

Submission status: Runtime Error

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


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

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

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

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

Submission status: Runtime Error

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


ans = []


def hoge(used, opened, price):
    if sum(opened) == n:
        ans.append(price)
        return 0
    for i in range(n):
        if opened[i] == 0:
            break
    for j in range(m):
        # print("j", j)
        if i + 1 in c[j] and i + 1 not in used:
            # print("if",j)
            used.append(j+1)
            for k in c[j]:
                opened[k-1] = 1
            price += a[j]
            hoge(used, opened, price)


opened = [0 for _ in range(n)]
hoge([], opened, 0)
print(min(ans))

Submission status: Runtime Error

Solution code:
from collections import defaultdict

d=defaultdict(list)
cost=[]

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

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


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

ans=0
key=set()

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])
    for i in li:
      for j in range(1,k):
        if i in d[j]:
          if ans>ans-li[0][0]-cost(i[1])+i[0]:
            ans=ans-li[0][0]-cost(i[1])+i[0]
            key.discard(li[0][1])
            key.add(i[1])
  
print(ans)

Submission status: Runtime Error

Solution code:
n, m = list(map(int, input().split()))
li = []
ans = 0
box = [0 for x in range(n)]
for i in range(m):
    a, b = list(map(int, input().split()))
    x = [a] + list(map(int, input()))
    li.append(x)

sorted(x)

for i in range(m):
    if 1 in x[i]:
        if x.index(1) >= 1:

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
l = []
for i in range(m):
  a, b = map(int, input().split())
  l += list(map(int, input().split())
for i in range(n):
  if (i+1) not in l:
    print(-1)
    quit()
print(1)