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())

x = [None for _ in range(m)]
for i in range(m):
    a, b = map(int, input().split())
    c = map(int, input().split())
    t = sum(map(lambda x: 2 ** (x - 1), c))
    x[i] = (a, t)

INF = 10 ** 9
dp_pre = [INF for _ in range(2 ** n)]
dp = [INF for _ in range(2 ** n)]
dp_pre[0] = 0
dp[0] = 0

for ai, ti in x:
    for j in range(2 ** n):
        dp[ti | j] = min(dp[ti | j], dp_pre[ti | j], dp_pre[j] + ai)
    dp_pre, dp = dp, dp_pre

if dp_pre[-1] >= INF:
    ans = -1
else:
    ans = dp_pre[-1]
print(ans)

Submission status: Wrong Answer

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

x = [None for _ in range(m)]
for i in range(m):
    a, b = map(int, input().split())
    c = map(int, input().split())
    t = sum(map(lambda x: 2 ** (x - 1), c))
    x[i] = (a, t)

INF = 10 ** 9
dp_pre = [INF for _ in range(2 ** n)]
dp = [INF for _ in range(2 ** n)]
dp_pre[0] = 0
dp[0] = 0

for ai, ti in x:
    for j in range(2 ** n):
        dp[ti | j] = min(dp[ti | j], dp_pre[ti | j], dp_pre[j] + ai)
    dp_pre, dp = dp, dp_pre

if dp_pre[-1] == INF:
    ans = -1
else:
    ans = dp_pre[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

x = [None for _ in range(m)]
y = 0
for i in range(m):
    a, b = map(int, input().split())
    c = map(int, input().split())
    t = sum(map(lambda x: 2 ** (x - 1), c))
    y = y | t
    x[i] = (a, t)

if y != 2 ** n - 1:
    print(-1)
    sys.exit()

INF = 10 ** 9
dp_pre = [INF for _ in range(2 ** n)]
dp = [INF for _ in range(2 ** n)]
dp_pre[0] = 0
dp[0] = 0

for ai, ti in x:
    for j in range(2 ** n):
        dp[ti | j] = min(dp[ti | j], dp_pre[ti | j], dp_pre[j] + ai)
    dp_pre, dp = dp, dp_pre

print(dp_pre[-1])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
b_cnt = 2 ** N #箱の数は最大12個
INF = 10 ** 9
dp = [INF] * b_cnt

for i in range(M):
    a, b = map(int, input().split())
    c = sum([2 ** (int(x)-1) for x in list(input().split())])
    for j in range(b_cnt):
        if dp[j|c] > dp[j] + a:
            dp[j|c] = dp[j] + a

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

Submission status: Wrong Answer

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

dp = dict()
tmp = [(0,0)]
while tmp != []:
    tmp2 = []
    for i in tmp:
        for j in l:
            if j[0] | i[0] != i[0]:
                ctmp = (j[0] | i[0] ,i[1] + j[1])
                if dp.get(ctmp[0],-1) == -1:
                    dp[ctmp[0]] = ctmp[1]
                    if ctmp[0] != 2**n - 1:
                        tmp2.append(ctmp)
                else:
                    if dp[ctmp[0]] > ctmp[1]:
                        dp[ctmp[0]] = ctmp[1]
                        if ctmp[0] != 2**n - 1:
                            tmp2.append(ctmp)
    print(tmp2)                        
    tmp = tmp2

print(dp.get(2**n-1,-1))

Submission status: Wrong Answer

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

key = {}
for mi in range(m):
  a,b = map(int,input().split())
  cc = list(map(int,input().split()))
  for ci in cc:
    if not (ci-1 in key):
      key[ci-1] = a
    else:
      if a < key[ci-1]:
        key[ci-1] = a

if len(key)<n:
  print(-1)
else:
  print(sum(key.values()))

Submission status: Wrong Answer

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

cost = [INF]*n
for mi in range(m):
  a,b = map(int,input().split())
  cc = list(map(int,input().split()))
  for ci in cc:
    cost[ci-1] = min(cost[ci-1],a)

if INF in cost:
  print(-1)
else:
  print(sum(set(cost)))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a_arr = []
b_arr = []
c_arr = []
 
dic = {0:0}
 
 
for i in range(m):
  a,b = map(int,input().split())
  a_arr.append(a)
  b_arr.append(b)
  tmp_arr = list(map(int, input().split()))
  
  arr = []
  for j in range(1, n+1):
    if j in tmp_arr:
      arr.append('1')
    else:
      arr.append('0')
  
  c = int(''.join(arr),2)
  
  dic2 = dic.copy()
  
  for k,v in dic.items():
    if (k|c) in dic.keys():
      dic2[k|c] = min(dic2[k|c],a+v)
    else:
      dic2[k|c] = a+v
 
  dic = dic2
 
if ((2**n)-1) in dic.keys():
  print(dic[(2**n) -1])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys

n,m = map(int,input().split())
a_arr = []
b_arr = []
c_arr = []

dic_arr = [{}]
dic_arr[0][0] = 0

for i in range(m):
  a,b = map(int,input().split())
  tmp_arr = list(map(int, input().split()))
  
  arr = []
  for j in range(1, n+1):
    if j in tmp_arr:
      arr.append('1')
    else:
      arr.append('0')
  
  c = int(''.join(arr),2)
  
  dic_arr.append(dic_arr[i].copy())
  
  for k,v in dic_arr[i].items():
    if (k|c) in dic_arr[i].keys():
      dic_arr[i+1][k|c] = min(dic_arr[i+1][k|c],a+v)
    else:
      dic_arr[i+1][k|c] = a+v
  
if ((2**n)-1) in dic_arr[m]:
  print(dic_arr[m][(2**n) -1])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import sys

n,m = map(int,input().split())
a_arr = []
b_arr = []
c_arr = []

dic_arr = [{}]
dic_arr[0][0] = 0

for i in range(m):
  a,b = map(int,input().split())
  a_arr.append(a)
  b_arr.append(b)
  tmp_arr = list(map(int, input().split()))
  
  arr = []
  for i in range(1, n+1):
    if i in tmp_arr:
      arr.append('1')
    else:
      arr.append('0')
  
  c_arr.append(int(''.join(arr),2))

for i in range(m):
  a = a_arr[i]
  b = b_arr[i]
  c = c_arr[i]
  
  dic_arr.append(dic_arr[i].copy())
  
  for k,v in dic_arr[i].items():
    if (k|c) in dic_arr[i].keys():
      dic_arr[i+1][k|c] = min(dic_arr[i+1][k|c],a+v)
    else:
      dic_arr[i+1][k|c] = a+v

if ((2**n)-1) in dic_arr[m]:
  print(dic_arr[m][(2**n) -1])
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
print(-1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a_arr = []
b_arr = []
c_arr = []

dic = {0:0}


for i in range(m):
  a,b = map(int,input().split())
  a_arr.append(a)
  b_arr.append(b)
  tmp_arr = list(map(int, input().split()))
  
  arr = []
  for i in range(1, n+1):
    if i in tmp_arr:
      arr.append('1')
    else:
      arr.append('0')
  
  c_arr.append(int(''.join(arr),2))

for i in range(m):
  a = a_arr[i]
  b = b_arr[i]
  c = c_arr[i]
  
  dic2 = dic.copy()
  
  for k,v in dic.items():
    if (k|c) in dic.keys():
      dic2[k|c] = min(dic2[k|c],a+v)
    else:
      dic2[k|c] = a+v

  dic = dic2
    
if ((2**n)-1) in dic.keys():
  print(dic[(2**n) -1])
else:
  print(-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 = list(map(int, input().split()))
    s = 0
    for j in range(b):
        s |= 1<<(c[j]-1)
    key.append([s, a])

INF = 10**8
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]
if ans == INF:
    print(-1)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    pw = 2 ** n
    dp = [10 ** 20] * pw
    dp[0] = 0
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        c = sum(2 ** (i - 1) for i in list(map(int, input().rstrip('\n').split())))
        for j in range(pw):
            if dp[j | c] > dp[j] + a:
                dp[j | c] = dp[j] + a
        print(dp)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    abl = []
    cl = []
    for i in range(m):
        abl.append(list(map(int, input().rstrip('\n').split())))
        cl.append(list(map(int, input().rstrip('\n').split())))
    dp = collections.defaultdict(list)
    mc = 10 ** 20
    for i in range(2 ** n + 1):
        bt = bin(i)[2:]
        st = set()
        if len(bt) == 0:
            bt = "0"
        if i == 0:
            dp[bt] += [st, 0]
        elif i == 1:
            for c in cl[len(bt)-1]:
                st.add(c)
            dp[bt] += [st, abl[len(bt)-1][0]]
        else:
            if len(bt) - 1 < m:
                st, cost = dp[str(int(bt[1:]))]
                for c in cl[len(bt)-1]:
                    st.add(c)
                dp[bt] += [st, cost + abl[len(bt)-1][0]]
        if len(st) == n:
            mc = min(mc, dp[bt][1])
    print(mc if mc != 10 ** 20 else -1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    abl = []
    cl = []
    for i in range(m):
        abl.append(list(map(int, input().rstrip('\n').split())))
        cl.append(list(map(int, input().rstrip('\n').split())))
    dp = [[set(), 0] for _ in range(2 ** n + 1)]
    mt = 10 ** 20
    #各bitを総検索
    for i in range(2 ** n + 1):
        bt = bin(i)
        #先頭bitに対して処理
        if i >= 1 and len(bt[2:]) - 1 < m:
            for c in cl[len(bt[2:])-1]:
                dp[i][0].add(c)
            dp[i][1] += abl[len(bt[2:])-1][0]
        #先頭bitより後ろのbitが同じパターンの解放済とコストを追加
        if i >= 2:
            for c in dp[int(bt[3:], 2)][0]:
                dp[i][0].add(c)
            dp[i][1] += dp[int(bt[3:], 2)][1]
        if len(dp[i][0]) == n:
            mt = min(mt, dp[i][1])
    print(mt if mt != 10 ** 20 else -1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m = list(map(int, input().rstrip('\n').split()))
    abl = []
    cl = []
    for i in range(m):
        abl.append(list(map(int, input().rstrip('\n').split())))
        cl.append(list(map(int, input().rstrip('\n').split())))
    dp = [[set(), 0] for _ in range(2 ** n + 1)]
    mt = 10 ** 20
    for i in range(2 ** n + 1):
        bt = bin(i)
        if i >= 1 and len(bt[2:])-1 < m:
            for c in cl[len(bt[2:])-1]:
                dp[i][0].add(c)
            dp[i][1] += abl[len(bt[2:])-1][0]
        if i >= 2 and len(bt[2:])-1 < m:
            for c in dp[int(bt[3:], 2)][0]:
                dp[i][0].add(c)
            dp[i][1] += dp[int(bt[3:], 2)][1]
        if len(dp[i][0]) == n:
            mt = min(mt, dp[i][1])
    print(mt if mt != 10 ** 20 else -1)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
def p_e():
    N, M = map(int, input().split())
    max_value = (10 ** 5) * 12 + 1
    dp_len = 2 ** N
    dp = [max_value] * dp_len
    dp[0] = 0
    for _ in range(M):
        a, b = map(int, input().split())
        keys = list(map(int, input().split()))
        index = 0
        for key in keys:
            index += 2 ** (key - 1)

        for i in range(dp_len):
            if dp[i] == max_value:
                continue
            dp_index = i | index
            dp[dp_index] = min(dp[dp_index], dp[i] + a)

    print(dp[-1])


if __name__ == '__main__':
    p_e()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M=map(int,input().split())
a=[0 for i in range(M)]
b=[0 for i in range(M)]
c=[0 for i in range(M)]
ac=[]
for m in range(M):
    a[m],b[m]=map(int,input().split())
    c[m]=list(map(int,input().split()))
    ac.append([[a[m]],c[m]])
ac.sort(key=lambda x:x[0])
cost=0
Boxes=np.array([])
flag=0
for AC in ac:
    A=AC[0]
    C=np.array(AC[1])
    for i in C:
        if not(i in Boxes):
            cost+=A[0]
            Boxes=np.concatenate([Boxes,C])
            Boxes=np.unique(Boxes)
    if len(Boxes)==N:
        flag=1
        break
if flag:
    print(cost)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from functools import reduce
N,M=map(int,input().split())
L=[]
p=2**N
for i in range(M):
    cost,_=map(int,input().split())
    k=reduce(lambda x,y: x+pow(2,y-1), map(int,input().split()))
    L.append([cost, k])

dp=[10**7]*p
dp[0]=0
for i in range(M):
    cost, k=L[i]
    for j in range(p):
        m=j|k
        dp[m]=min(dp[m],dp[j]+cost)
print(dp[-1] if dp[-1]!=10**7 else -1)

Submission status: Wrong Answer

Solution code:
# 入力（長い...）
N, M = [int(i) for i in input().split()]
A, B, C = [], [], []
for _ in range(M):
    a, b = [int(i) for i in input().split()]
    A.append(a)
    B.append(b)
    C.append({int(i) for i in input().split()})
    
# 鍵の種類の和集合（allc）を求め、これがNと一致しなければ-1で終了
allc = set()
for c in C:
    allc = allc.union(c)
if len(allc) != N:
    print(-1)
    exit(0)
else:
    print(allc)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from heapq import heappop, heappush
N, M = map(int, input().split())
A = []
B = []
C = []
D = defaultdict(list)
S = set()
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    c = list(map(int, input().split()))
    for x in c:
        heappush(D[x], (A[i], i))
    S |= (set(c))
    C.append(c)

if len(S) < N:
    print(-1)
    exit()

ans = 0
check = [0]*(N+1)
check[0] = 1
for key in D:
    if len(D[key]) == 1:
        a, i = D[key][0]
        ans += a
        for n in C[i]:
            check[n] = 1

compare = set()
for n in range(1, N+1):
    if check[n] == 0:
        compare.add(n)


while compare:
    Q = []
    tmp = dict()
    for n in list(compare):
        a, i = heappop(D[n])
        tmp[n] = (a, i)
        heappush(Q, (a, i))
    min_a, i = heappop(Q)
    ans += min_a
    for n in C[i]:
        if n in compare:
            compare.remove(n)
    for n in list(compare):
        heappush(D[n], tmp[n])

print(ans)

Submission status: Wrong Answer

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

if len(S) < N:
    print(-1)
    exit()

ans = 0
check = [0]*(N+1)
check[0] = 1
for key in D:
    if len(D[key]) == 1:
        a, i = D[key][0]
        ans += a
        for n in C[i]:
            check[n] = 1

compare = []
for n in range(1, N+1):
    if check[n] == 0:
        compare.append(n)

from heapq import heappop, heappush
Q = []
for n in compare:
    for a, i in D[n]:
        heappush(Q, (a, i))

while not all(check):
    a, i = heappop(Q)
    flag = False
    for n in C[i]:
        if check[n] == 0:
            flag = True
            break
    if flag:
        ans += a
        for n in C[i]:
            check[n] = 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda:sys.stdin.readline()
MOD = 1000000007
ii = lambda: int(input())
si = lambda: input()
dgl = lambda: list(map(int, input()))
f = lambda: list(map(int, input().split()))
il = lambda: list(map(int, input().split()))
ls = lambda: list(input())
d=dict()
n, m = f()
l=[]
for i in range(m):
    an,bn=f()
    l.append([an, i])
    d[i]=set(il())
l.sort()
s=set()
sm=0
for i in l:
    x=s.union(d[i[1]])
    if len(x) > len(s):
        s=x
        sm += i[0]
print(sm if len(s)==n else -1)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda:sys.stdin.readline()
MOD = 1000000007
ii = lambda: int(input())
si = lambda: input()
dgl = lambda: list(map(int, input()))
f = lambda: list(map(int, input().split()))
il = lambda: list(map(int, input().split()))
ls = lambda: list(input())
s=set()
d=dict()
n, m = f()
for _ in range(m):
    an,bn=f()
    l=il()
    for i in l:
        if not i in d:
            d[i]=[[an,_]]
        else:
            d[i].append([an,_])
ans=0
for i in d:
    d[i].sort()
    if not d[i][0][1] in s:
        ans+=d[i][0][0]
        s.add(d[i][0][1])
print(ans if len(d)==n else -1)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda:sys.stdin.readline()
MOD = 1000000007
ii = lambda: int(input())
si = lambda: input()
dgl = lambda: list(map(int, input()))
f = lambda: list(map(int, input().split()))
il = lambda: list(map(int, input().split()))
ls = lambda: list(input())
s=set()
d=dict()
n, m = f()
for _ in range(m):
    an,bn=f()
    l=il()
    for i in l:
        if not i in d:
            d[i]=[[an,_]]
        else:
            d[i].append([an,_])
ans=0
for i in d:
    d[i].sort()
    if not d[i][0][1] in s:
        ans+=d[i][0][0]
        s.add(d[i][0][1])

print(ans if len(s)==n else -1)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda:sys.stdin.readline()
MOD = 1000000007
ii = lambda: int(input())
si = lambda: input()
dgl = lambda: list(map(int, input()))
f = lambda: list(map(int, input().split()))
il = lambda: list(map(int, input().split()))
ls = lambda: list(input())
s=set()
d=dict()
n, m = f()
for _ in range(m):
    an,bn=f()
    l=il()
    for i in l:
        if not i in d:
            d[i]=[[an,_]]
        else:
            d[i].append([an,_])
ans=0
for i in d:
    d[i].sort()
    if not d[i][0][1] in s:
        ans+=d[i][0][0]
        s.add(d[i][0][1])
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
a = [0] * M # 鍵の値段
c = [[]] * M
INF = 100000001
dp = [INF for i in range(2 ** N)]
for i in range(M):
    a[i], _ = map(int, input().split())
    c[i] = list(map(int, input().split()))

b = []
for l in c:
    g = 0
    for n in l:
        g |= 1 << (n - 1)
    b.append(g)

l = 2 ** N
print(l)
dp[0] = 0
for s in range(l):
    for i in range(M):
        p = s | b[i]
        dp[p] = min(dp[p], dp[s] + a[i])
ans = dp[-1]
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

n,m = map(int, input().split()) #n: treasure num, m: key num
a,b,c = [0]*m, [0]*m, [0]*m     #a: key's cost, b: key's treasure num, c(list of int list): key's treasure kind
for i in range(m):
    a[i], b[i] = map(int, input().split())
    c[i] = list(map(int, input().split()))

#cost[n_i][m_i] mean key m_i have lowest cost to unlock treasure n_i 
cost = np.full((n,m), np.inf)

for i in range(m):
    for j in c[i]:
        if cost[j-1][i] > a[i]:
            cost[j-1][i] = a[i]

buy = set()
for ni in range(n):
    if all(key == np.inf for key in cost[ni]):
        print(-1)
        sys.exit()
    else:
        buy.add(np.argmin(cost[ni]))

ans = sum(a[mi] for mi in buy)
print(int(ans))

Submission status: Wrong Answer

Solution code:
import numpy as np

n,m = map(int, input().split()) #n: treasure num, m: key num
a,b,c = [0]*m, [0]*m, [0]*m     #a: key's cost, b: key's treasure num, c(list of int list): key's treasure kind
for i in range(m):
    a[i], b[i] = map(int, input().split())
    c[i] = list(map(int, input().split()))

#cost[n_i][m_i] mean key m_i have lowest cost to unlock treasure n_i 
cost = np.full((n,m), np.inf)

for i in range(m):
    for j in c[i]:
        if cost[j-1][i] > a[i]:
            cost[j-1][i] = a[i]

buy = {np.argmin(cost[ni]) for ni in range(n)}
ans = sum(a[mi] for mi in buy)
if ans < np.inf:
    print(int(ans))
else:
    print(-1)

Submission status: Wrong Answer

Solution code:

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd as bltin_gcd

a, b = [int(x) for x in input().split()]

d = 1
d_list = []
while(d <= a and d <= b):
  if a % d == 0 and b % d == 0:
    d_list.append(d)
  d += 1

length = len(d_list)

answer = 0
is_sosu = True
for i in range(length):
  is_sosu = True
  for j in range(length):
    if i != j:
      if bltin_gcd(d_list[i],d_list[j]) != 1:
        is_sosu = False
        length = len(d_list)
        break
  if not is_sosu:
    answer += 1
print(answer)

Submission status: Wrong Answer

Solution code:
from fractions import gcd as bltin_gcd

a, b = [int(x) for x in input().split()]

d = 1
d_list = []
while(d <= a and d <= b):
  if a % d == 0 and b % d == 0:
    d_list.append(d)
  d += 1

count = 0
length = len(d_list)

answer = 0
is_sosu = True
for i in range(length):
  is_sosu = True
  for j in range(length):
    print(d_list[i],d_list[j], i==j, is_sosu, bltin_gcd(d_list[i],d_list[j]))
    if i != j:
      if bltin_gcd(d_list[i],d_list[j]) != 1:
        is_sosu = False
        length = len(d_list)
        break
  if not is_sosu:
    answer += 1
print(answer)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# if x < y:
#     z = x
# elif True:
#     z = y
# else:
#     z = 100
import sys,os,math
from collections import Counter, defaultdict
import bisect
from sys import stdin, stdout
from itertools import repeat


# n, k = map(int, raw_input().split())
# da = map(int, raw_input().split())
# db = map(int, raw_input().split())

def main():
    n, m = map(int, raw_input().split())
    bf, af = [10000000 for i in range(1<<n)], [10000000 for i in range(1<<n)]
    bf[0] = 0
    for i in range(m):
        a, b = map(int, raw_input().split())
        ad = 0
        for st in map(int, raw_input().split()):
            ad |= 1<<(st-1)

        for st in range(1<<n):
            af[st|ad] = min(bf[st|ad], bf[st]+a, af[st|ad])
        # print af
        bf, af = af, bf
    if bf[(1<<n)-1] == 10000000:
        print -1
    else:
        print bf[(1<<n)-1]



main()

Submission status: Wrong Answer

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

inf = 10**9

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M = map(int, input().split())
inf = 10**9
dp = np.zeros((M + 1, 2**N), dtype = 'int') + inf 
# dp[i][j] := i個目までの鍵を使うときの状態jを実現する最小費用 # 0列目は使わない
# 行 : 0番目の鍵 ~ M - 1番目の鍵
# 列 : 状態0 ~ 2**N - 1

dp[0][0] = 0

for i in range(1, M + 1):
    a, b = map(int, input().split())
    c_ls = map(int, input().split())
    d = 0 # i番目の鍵が開けられる宝箱の状態
    for c in c_ls:
        d += 2**(c - 1)
    for j in range(2**N):
        jord = np.bitwise_or(j, d)
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        dp[i][jord] = min(dp[i - 1][j] + a, dp[i][jord])
#         if i == 1:
#             print(dp[i][jord], i, jord, j, d, np.bitwise_or(j, d))
        
if dp[M][2**N - 1] == np.inf:
    print(- 1)
else:
    print(dp[M][2**N - 1])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = np.zeros((M + 1, 2**N), dtype = 'int') + np.inf 
dp[0][0] = 0

for i in range(1, M + 1):
    a, b = map(int, input().split())
    c_ls = map(int, input().split())
    d = 0 
    for c in c_ls:
        d += 2**(c - 1)
    for j in range(2**N):
        jord = np.bitwise_or(j, d)
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        dp[i][jord] = min(dp[i - 1][j] + a, dp[i][jord])

if dp[M][2**N - 1] == np.inf:
    print(- 1)
else:
    print(dp[M][2**N - 1])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = [10e9] * (2 ** N)
dp[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    c = map(int, input().split())
    key = np.sum([2**(x-1) for x in c])
    
    ndp = dp.copy()
    for j in range(2**N):
        if dp[j | key] > ndp[j] + a:
            dp[j | key] = ndp[j] + a
            
if dp[-1] == np.inf:
  print(-1)
else:
  print(dp[-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp = [2e9] * (2 ** N)
dp[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    c = map(int, input().split())
    key = np.sum([2**(x-1) for x in c])
    
    ndp = dp.copy()
    for j in range(2**N):
        if dp[j | key] > ndp[j] + a:
            dp[j | key] = ndp[j] + a
            
if dp[-1] == np.inf:
  print(-1)
else:
  print(dp[-1])

Submission status: Wrong Answer

Solution code:
import sys
import copy

n_box, n_key = [int(item) for item in input().strip().split(' ')]
price = []
box_openable = []
for _ in range(n_key):
    a, _ = [int(item) for item in input().strip().split(' ')]
    c = [int(item) for item in input().strip().split(' ')]
    price.append(a)
    box_openable.append(c)

# 箱nを開けられる鍵がどれかを考える
key_for_certain_box = []
for n in range(1, n_box+1):
    key_for_certain_box.append([])
    for idx, b in enumerate(box_openable):
        if n in b:
            key_for_certain_box[-1].append(idx)
    if key_for_certain_box[-1] == []:
        print(-1)
        sys.exit()

def recursive(key, remain, current_price):
    # key番目の鍵を選んだ場合に、同じ鍵で開けることができる宝箱をremainから取り除き、
    # 依然開けられない宝箱のidxを返す
    delete_indices = []
    for i in range(len(remain)):
        if key in remain[i]:
            delete_indices.append(i)
    for delete_idx in delete_indices[::-1]:
        del remain[delete_idx]

    if remain == []:
        price_list.append(current_price)
    else:
        for key in remain[0]:
            recursive(key, remain, current_price + price[key])

key_for_certain_box_copy = copy.copy(key_for_certain_box)
price_list = []
for key in key_for_certain_box[0]:
    current_price = price[key]
    recursive(key, key_for_certain_box_copy, current_price)
print(min(price_list))