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: Accepted

Solution code:
#E https://atcoder.jp/contests/abc142/submissions/7853616
def main():
    n, m = map(int, input().split())
    inf = 10**9 #この10億は何に使う？->とにかくデカい数字。
    bit_dp = [inf for _ in range(2**(n))] #10億を2**n個並べる配列を作る。n=12 => 4096個
    bit_dp[0] = 0
    for i in range(m):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))#鍵1個につきa,b,c1~cbを決める
        bit_n = 0
        for i in c:
            bit_n |= 1 << i - 1 #ここで何番目をあけられるのかをbit_nで定義する。1と3ならbit_n=(5)101、2と3なら110(6)
        for i in range(2**n):
            if bit_dp[i|bit_n] > bit_dp[i] + a:
                bit_dp[i|bit_n] = bit_dp[i] + a
    if bit_dp[-1] >= inf:
        print(-1)
    else:
        print(bit_dp[-1])
                
if __name__ == "__main__":
    main()

Submission status: Accepted

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

INF = 10**9
array_len = int(math.pow(2, N))

min_array = [INF] * array_len

min_array[0] = 0

for _ in range(M):
    a, b = map(int, input().split())
    c_array = map(int, input().split())
    key_sum = 0
    for c in c_array:
        key_sum += int(math.pow(2, c - 1))
    for i in range(array_len):
        if min_array[i] == INF:
            continue
        else:
            min_array[i | key_sum] = min(min_array[i | key_sum],
                                         min_array[i] + a)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
pp = []
for _ in range(M):
  a, b = map(int, input().split())
  cc = map(int, input().split())
  bit = 0
  for c in cc:
    bit += 1 << (c - 1)
  pp.append((a, bit))

inf = 10000000

S = 1 << N
dp = [inf] * S
dp[0] = 0
for s in range(1, S):
  for a, bit in pp:
    dp[s] = min(dp[s], a + dp[s - (s & bit)])
if dp[S-1] >= inf:
  print(-1)
else:
  print(dp[S-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
import heapq

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)

    def get_size(self, x):
        """
        x が属するグループの要素数
        """
        x = self.find(x)
        return self.size[x]
    

"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

#Distance Transformation
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                pass
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)

"""


N, M = list(map(int, input().split()))
AB = [None]*M

C = [0]*M
for m in range(M):
    AB[m] = list(map(int, input().split()))
    c = list(map(int, input().split()))
    key = 0
    for k in c:
        key += 2**(k-1)
    C[m] = key
    
    
def main():
    inf = 10**9
    num_s = 2**N
    dp = [inf]*(num_s)
    dp[0] = 0
    for n in range(num_s):
        for m in range(M):
            l = n | C[m]
            dp[l] = min(dp[l], dp[n]+AB[m][0])
            
    #print(C)
    #print(dp)
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
arr=[]
for _ in range(m):
  a,b=map(int,input().split())
  tl=list(map(int,input().split()))
  tmp=0
  for val in tl:
    tmp+=2**(val-1)
  arr.append((a,tmp))
dp=[10**18]*(2**n)
dp[0]=0
for val,flag in arr:
  for i in range(2**n-1,-1,-1):
    if dp[i]==10**18:
      continue
    else:
      dp[i|flag]=min(dp[i|flag],dp[i]+val)
if dp[-1]==10**18:
  print(-1)
else:
  print(dp[-1])

Submission status: Accepted

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]+a, af[st|ad])
            af[st] = min(af[st], bf[st])
        bf, af = af, bf
    if bf[(1<<n)-1] == 10000000:
        print -1
    else:
        print bf[(1<<n)-1]


main()

Submission status: Accepted

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])
            af[st] = min(af[st], bf[st])
        bf, af = af, bf
    if bf[(1<<n)-1] == 10000000:
        print -1
    else:
        print bf[(1<<n)-1]



main()

Submission status: Accepted

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])
        for st in range(1<<n):
            af[st] = min(af[st], bf[st])
        bf, af = af, bf
    if bf[(1<<n)-1] == 10000000:
        print -1
    else:
        print bf[(1<<n)-1]



main()

Submission status: Accepted

Solution code:
#dpがやや特殊なので、1次元的に走査したほうがよさそう。initializeもいらないし。
n,m = map(int, input().split())

inf = 10**9

dp =[inf for _ in range(2**n)]
dp[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
        dp[jord] = min(dp[jord], dp[j] + a)
            
if dp[-1] == inf:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return [int(i)-1 for i in input().split()]
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    ans = 0
    for i in range(1, n + 1):
        ans += i & 1
    print(ans/n)
    return

#B
def B():
    n, k = LI()
    h = LI()
    ans = 0
    for i in h:
        ans += i >= k
    print(ans)
    return

#C
def C():
    n = II()
    a = LI()
    d = defaultdict(int)
    for i in range(n):
        d[a[i] + 1] = i + 1
    for _, v in sorted(d.items()):
        print(v, end=" ")
    print()
    return

def primes(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    """ 6以上の数であれば p (素数) <= n のlistを返す """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1,int(n**0.5)//3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      k*k//3      ::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

#D
def D():
    a, b = LI()
    da = defaultdict(int)
    db = defaultdict(int)
    for i in range(2, int(math.sqrt(a)) + 1):
        while a % i == 0:
            a = a // i
            da[i] = 1
        while b % i == 0:
            b = b // i
            db[i] = 1
    da[a] = 1
    db[b] = 1
    da[1] = 1
    db[1] = 1
    print(len(set(da.keys()) & set(db.keys())))
    return

#E
def E():
    n, m = LI()
    dp = [inf] * (1 << n)
    dp[0] = 0
    for _ in range(m):
        a, b = LI()
        c = LI_()
        fulls = sum((1<<c[i] for i in range(b)))
        for i in range(1 << n):
            dp[i | fulls] = min(dp[i | fulls], dp[i] + a)
    if dp[-1] == inf:
        print(-1)
    else:
        print(dp[-1])
    return

#F
def F():
    return

#Solve
if __name__ == '__main__':
    E()

Submission status: Accepted

Solution code:
import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
A = []
B = []
C = []
for mm in range(M):
    tmpa, tmpb = MAP()
    A.append(tmpa)
    B.append(tmpb)
    tmpc = LIST()
    c = 0
    for cc in tmpc:
        c += 2**(cc-1)
    C.append(c)

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

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split(" ")))
abc = [[0, 0, 0] for i in range(M)]
for i in range(M):
  abc[i][0], abc[i][1] = list(map(int, input().split(" ")))
  c = list(map(int, input().split(" ")))
  for j in c:
    cbits = (1 << j-1) 
    abc[i][2] |= cbits

dp = [0 if i == 0 else float("inf") for i in range(2**N)]
for i in range(M):
  for j in range(2**N):
    if dp[j|abc[i][2]] > dp[j]+abc[i][0]:
      dp[j|abc[i][2]] = dp[j]+abc[i][0]
print(dp[-1] if dp[-1] != float("inf") else -1)

Submission status: Accepted

Solution code:
def bit_op(i,j):
    a = i&j
    return i ^ a


N = [int(i) for i in input().split()]

a = [0]*N[1]
b = [0]*N[1]
c = []

for k in range(N[1]):
    inp = [int(i) for i in input().split()]
    a[k] = inp[0]
    b[k] = inp[1]

    key = [int(i) for i in input().split()]

    c.append(key)
    
#print(a)
#print(b)
#print(c)

c_two = []

for k in range(N[1]):
    key=0
    for i in range(len(c[k])):
        key = key | 2**(c[k][i]-1)
    
    #print(key)
    c_two.append(key)

#print(c_two)

max_j = 2**N[0]

val = [1000000] * max_j

for i in range(N[1]):

    for j in range(max_j):
        j2 = bit_op(j, c_two[i])
        if j2 == 0 :
            if a[i] < val[j] :
                val[j] = a[i]
        else :
            if (val[j2] + a[i]) < val[j]:
                val[j] = val[j2] + a[i]

if val[max_j-1] == 1000000:
    print(-1)
else:
    print(val[max_j-1])

Submission status: Accepted

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

INF = 10**7
dp = [INF]*2**N
dp[0] = 0
bits = set()
bits.add(0)
for i in range(M):
    a, b = map(int, input().split())
    d = sum((1<< (i - 1)) for i in  map(int, input().split()))
    add_set = set() # i個目の鍵を使ってbitsに新しく追加する分の状態を入れる
    for j in bits:
        jord = j | d
        dp[jord] = min(dp[jord], dp[j] + a)
        add_set.add(jord)
    bits |= add_set
    
if dp[- 1] == INF:
    print(- 1)
else:
    print(dp[- 1])

Submission status: Accepted

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

INF = 10**7
dp = [INF]*2**N
dp[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):
        if dp[j] == INF:
            continue
        jord = j | d
        dp[jord] = min(dp[j] + a, dp[jord])
        
if dp[- 1] == INF:
    print(- 1)
else:
    print(dp[- 1])

Submission status: Accepted

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

INF = 10**7
dp = [INF]*2**N
dp[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    c_ls = map(int, input().split())
    #d = sum((1<< (i - 1)) for i in  map(int, input().split()))  
    d = 0
    for c in c_ls:
        d += 2**(c - 1)
    for j in range(2**N):
        jord = j | d
        dp[jord] = min(dp[j] + a, dp[jord])
        
if dp[- 1] == INF:
    print(- 1)
else:
    print(dp[- 1])

Submission status: Accepted

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

INF = 10**7
dp = [INF]*2**N
dp[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
        dp[jord] = min(dp[j] + a, dp[jord])
        
if dp[- 1] == INF:
    print(- 1)
else:
    print(dp[- 1])

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
vals = []
inf = float("inf")
res = [inf]*2**n

for i in range(m):
	a,b = map(int,input().split())
	C = list(map(int,input().split()))
	cur = 0
	for c in C:
		cur |= 2**(c-1)
	res[cur] = min(res[cur],a)

ans = []
for i,r in enumerate(res):
	if res[i] == inf:
		continue
	ans.append([i,r])


for i,a in ans:
	for j in range(2**n):
		res[i|j] = min(res[i|j],res[i]+res[j])

if res[-1] == inf:
	print(-1)
else:
	print(res[-1])

Submission status: Accepted

Solution code:
def main():
  n,m=map(int,input().split())
  a=[0 for i in range(m)]
  b=[0 for i in range(m)]
  c=[[] for i in range(m)]
  for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=list(map(int,input().split()))
  
  dp=[float("inf") for i in range(2**n)]
  dp[0]=0
  for i in range(m):
    now=0
    for j in c[i]:
      jj=1<<j-1
      now|=jj
    for k in range(2**n):
      kk=k|now
      dp[kk]=min(dp[kk],dp[k]+a[i])
    
 
  if dp[-1]==float("inf"):
    print(-1)
  else:
    print(dp[-1])
    
if __name__ == '__main__':  
  main()

Submission status: Accepted

Solution code:
from sys import setrecursionlimit as SRL, stdin

SRL(10 ** 7)
rd = stdin.readline
rrd = lambda: map(int, rd().strip().split())
n, m = rrd()

e = [[] for _i in range(1 << 13)]

p = []
for i in range(m):
    a, b = rrd()
    lst = list(rrd())
    g = 0
    for j in lst:
        g |= 1 << (j - 1)
    p.append((a, g))

for i in range(1 << n):
    for j in p:
        e[i].append((i | j[1], j[0]))
inf = 10**10

dis = [inf] * (1 << 13)
vis = [0] * (1 << 13)
dis[0] = 0

from heapq import *

q = [(0, 0)]
while len(q):
    ds, now = heappop(q)
    if vis[now]:
        continue
    vis[now] = 1
    for next, cost in e[now]:
        if dis[next] > dis[now] + cost:
            dis[next] = dis[now] + cost
            heappush(q, (dis[next], next))

if dis[(1 << n) - 1] == inf:
    print(-1)
else:
    print(dis[(1 << n) - 1])

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    a = []
    c = []
    dp = [10 ** 7 for j in range(2 ** n)]
    dp[0] = 0
    for _ in range(m):
        a, b = map(int, input().split())
        sc = list(map(int, input().split()))
        c = 0
        for j in sc:
            c += 2 ** (j - 1)
        for j in range(2 ** n):
            dp[j | c] = min(dp[j | c], dp[j] + a)

    if dp[2 ** n - 1] == 10 ** 7:
        print(-1)
    else:
        print(dp[2 ** n - 1])


main()

Submission status: Accepted

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


N, M = map(int, input().split())
INF = 10**9
dp = [INF] * (2**N)
dp[0] = 0

for _ in range(M):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  bit = 0
  for i in c:
    bit |= 1 << (i-1)
  for i in range(2**N):
    if dp[i|bit] > dp[i] + a:
      dp[i|bit] = dp[i] + a
if dp[-1] >= INF:
  print(-1)
else:
  print(dp[-1])

Submission status: Accepted

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

memo = [MAX for i in range(10000)]
memo[0] = 0
a = []
c = []
for i in range(M):
	tmpa, tmpb = map(int, input().split())
	tmpc = list(map(int, input().split()))
	bitc = 0
	for tmp in tmpc:
		tmp = tmp - 1
		bitc = bitc | (1<<tmp)
	a.append(tmpa)
	c.append(bitc)

for i in range(M):
	cost = a[i]
	bit = c[i]
	for idx in range(10000 - 1, -1, -1):
		if(memo[idx] < MAX):
			to = idx | bit
			memo[to] = min(memo[to], memo[idx] + cost)
if(memo[2**N - 1] != MAX):
	print(memo[2**N-1])
else:
	print(-1)

Submission status: Accepted

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

    inf = 10**7
    dp = [inf]*(2**N)
    dp[0] = 0

    for i in range(M):
        a,b = map(int, input().split())
        c = list(map(int, input().split()))
        bit_c = 0
        for bi in c:
            bit_c |= 1 << bi-1
        #print(bit_c)
        for j in range(2**N):
            dp[j|bit_c] = min(dp[j] + a, dp[j|bit_c])

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict

MX = 10**10


def getInt(cn):
  ret = 0
  for c in cn:
    ret += 2**(c-1)
  return ret


## input
N,M = map(int, input().split())
Prices = defaultdict(lambda:MX)
for _ in range(M):
  a,b = map(int, input().split())
  cn = list(map(int, input().split()))
  Prices[getInt(cn)] = min(Prices[getInt(cn)],a)

dp = [MX for _ in range(2**N)]
dp[0] = 0
for p in Prices:
  for i in range(2**N):
    dp[i|p] = min(dp[i|p],dp[i]+Prices[p])

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

Submission status: Accepted

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

dp = [float('inf')] * (2 ** N)
dp[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    key = 0
    for x in c:
      key += 2 **(x-1)
    
    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] == float('inf'):
  print(-1)
else:
  print(dp[-1])

Submission status: Accepted

Solution code:
INF = float('inf')
N, M = map(int, input().split())
dp = [INF for _ in range(2**N)]
dp[0] = 0
for i in range(M):
    a, _ = map(int, input().split())
    *C, = map(int, input().split())
    open_bit = 0
    for i in C: open_bit |= 1 << i-1
    for i in range(2**N):
        temp = dp[i] + a
        if dp[i|open_bit] > temp: dp[i|open_bit] = temp
if dp[-1] != INF: print(dp[-1])
else: print(-1)

Submission status: Accepted

Solution code:
INF = float('inf')
N, M = map(int, input().split())
dp = [INF for _ in range(2**N)]
dp[0] = 0
for i in range(M):
    a, _ = map(int, input().split())
    *C, = map(int, input().split())
    open_bit = 0
    for i in C: open_bit |= 1 << i-1
    for i in range(2**N):
        temp = dp[i] + a
        if dp[i|open_bit] > temp: dp[i|open_bit] = temp
print(dp[-1] if dp[-1] != INF else -1)

Submission status: Accepted

Solution code:
def main():
    INF = float('inf')
    N, M = map(int, input().split())
    dp = [INF for _ in range(2**N)]
    dp[0] = 0
    for i in range(M):
        a, _ = map(int, input().split())
        *C, = map(int, input().split())
        open_bit = 0
        for i in C: open_bit |= 1 << i-1
        for i in range(2**N): dp[i|open_bit] = min(dp[i|open_bit], dp[i] + a)
    print(dp[-1] if dp[-1] != INF else -1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

N, K = map(int, input().split())
key_data_list = []
for _ in range(K):
    value, op = map(int, input().split())
    open_boxes = map(int, input().split())
    box_value = 0
    for opb in open_boxes:
      box_value += 2**(opb-1)
    key_data_list.append([value, box_value])

max_tresure_state = 2**N
max_key_price = 2**30
dp_table = [[max_key_price] * (max_tresure_state) for i in range(K+1)]

dp_table[0][0] = 0

for key_index in range(K):
    for tresure_state in range(max_tresure_state):
        key_value = key_data_list[key_index][0]
        key_state = key_data_list[key_index][1]

        if dp_table[key_index+1][tresure_state] > dp_table[key_index][tresure_state]:
            dp_table[key_index+1][tresure_state] = dp_table[key_index][tresure_state]

        buying_state = key_state | tresure_state
        dp_table[key_index+1][buying_state] = min(dp_table[key_index][buying_state],
                                                  dp_table[key_index+1][buying_state],
                                                  dp_table[key_index][tresure_state] + key_value)


result_value = dp_table[K][max_tresure_state-1]
if result_value == max_key_price:
    print(-1)
else:
    print(int(result_value))

Submission status: Accepted

Solution code:
INF = 10 ** 10
n, m = map(int, input().split())
k = (1 << n) - 1
lst = [[INF for j in range(k+1)] for i in range(m+1)]
lst[0][0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c = sum([1 << (x-1) for x in tuple(map(int, input().split()))])
    for j in range(k+1):
        if lst[i][j] != INF:
            lst[i+1][j | c] = min(lst[i+1][j | c], lst[i][j] + a)
            lst[i+1][j] = min(lst[i+1][j], lst[i][j])

print(lst[m][k] if lst[m][k] != INF else -1)

Submission status: Accepted

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

inf = 10 ** 10

dp = [inf] * (1 << N)
dp[0] = 0
#print(dp)


for _ in range(M):
    a, b = map(int, input().split())
    c = sum([2 ** (i - 1) for i in map(int, input().split())])
    #print(a, b)
    #print(c)

    for j in range(1 << N):
      dp[j | c] = min(dp[j] + a, dp[j | c])
      # print(j | c)
res = dp[-1] if dp[-1] != inf else -1
print(res)

Submission status: Accepted

Solution code:
def main():
    n ,m = map(int, input().split(' '))
    inf = 10**9
    bit_dp = [inf for _ in range(2**(n))]
    bit_dp[0] = 0
    for i in range(m):
        a, b = map(int, input().split(' '))
        c = list(map(int, input().split(' ')))
        bit_n = 0
        for i in c:
            bit_n |= 1 << i-1
        for i in range(2**(n)):
            if bit_dp[i|bit_n] > bit_dp[i] + a:
                bit_dp[i|bit_n] = bit_dp[i] + a
    if bit_dp[-1] >= inf:
        print(-1)
    else:
        print(bit_dp[-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
V = []
INF = float("inf")
dp = [INF]*(1<<N)
dp[0] = 0
for i in range(M):
  a,b = map(int, input().split())
  c = list(map(int, input().split()))
  k = 0
  for j in range(b):
    k += 1<<(c[j]-1)
  V.append((a,k))
  dp[k] = min(dp[k],a)

for i in range(1<<N):
  for a,k in V:
    dp[i|k] = min(dp[i|k],dp[i]+dp[k])  
print(dp[-1] if dp[-1] != INF else -1)

Submission status: Accepted

Solution code:
def main():
    n ,m = map(int, input().split(' '))
    inf = 10**9
    bit_dp = [inf for _ in range(2**(n))]
    bit_dp[0] = 0
    for i in range(m):
        a, b = map(int, input().split(' '))
        c = list(map(int, input().split(' ')))
        bit_n = 0
        for i in c:
            bit_n |= 1 << i-1
        for i in range(2**(n)):
            bit_dp[i|bit_n] = min(bit_dp[i|bit_n], bit_dp[i] + a)
    if bit_dp[-1] >= inf:
        print(-1)
    else:
        print(bit_dp[-1])
if __name__ == '__main__':
    main()