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:
INF = 10 ** 9 + 1

N, M = map(int, input().split())
key = []
for i in range(M):
    a, b = map(int, input().split())

    line = list(map(int, input().split()))
    s = 0
    for c in line:
        c -= 1
        s |= 1<<c
    key.append((s, a))

dp = [INF] * (1<<N)
dp[0] = 0
for s in range(1<<N):
    for state, val in key:
        t = s | state
        cost = dp[s] + val
        dp[t] = min(dp[t], cost)


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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        key = []
        for _ in range(M):
            a, b = map(int, input().split())
            s = 0
            for box_num in map(int, input().split()):
                s |= 1 << (box_num - 1)
            key.append([a, s])

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

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


# Run main
if __name__ == '__main__':
    AtCoder().main()

Submission status: Accepted

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

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

S = []

for m in range(M):
    A, B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    s = 0
    for c in C:
        s |= 1 << (c-1)
    S.append((s, A))

DP = [float("inf")] * (1 << N)
DP[0] = 0

for i in range(1 << N):
    for s, a in S:
        t = i | s
        DP[t] = min(DP[t], DP[i] + a)

if DP[-1] == float("inf"):
    print(-1)
    sys.exit(0)

print(DP[-1])

Submission status: Accepted

Solution code:
#パクリ

def main():
    N, M = map(int, input().split())
    inf = int(1e10)
    #print(inf)
    dp = [inf] * (2**N) #1をNだけシフトする 2**B
    
    
    #鍵をビットで表す　dp[i]は鍵の状態iにできる最小費用を
    dp[0] = 0
    bits = set()
    bits.add(0)
    #print(dp)
    for i in range(M):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        # cを状態keyに変換
        key = 0
        for t in c:
            key += 1 << (t - 1)
        ##print(c,">>",key)
        # bits内のbitとkeyのORを更新
        # 更新したbitはbitsに追加
        add_bits = set()
        for bit in bits:
            tmp = bit | key
            #print("key>>",key,"bit>>",bit,"tmp>>",tmp)
            #print("dp>>",dp)
            if dp[bit] + a < dp[tmp]:
                dp[tmp] = dp[bit] + a
                add_bits.add(tmp)
        #print("bits>>",bits)
        #print("addadd_bits>>",bits)

        bits = add_bits|bits
        #print(">>>bits>>",bits)
    
    if dp[(1 << N) - 1] == inf:
        print(-1)
    else:
        print(dp[(1 << N) - 1])
    #print(dp)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import array
import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


INF = 2 ** 31 - 1


def solve(N, M, A, B, C):
    D = []
    for c in C:
        b = 0
        for v in c:
            b |= 1 << (v - 1)
        D.append(b)

    bits = 1 << N
    dp = array.array('i', [INF] * bits)

    dp[0] = 0
    for a, d in zip(A, D):
        for b in range(bits):
            if dp[b] == INF:
                continue
            nb = b | d
            dp[nb] = min(dp[nb], dp[b] + a)

    if dp[bits - 1] == INF:
        return -1
    return dp[bits - 1]


def main():
    N, M = [int(e) for e in inp().split()]
    A = []
    B = []
    C = []
    for _ in range(M):
        a, b = [int(e) for e in inp().split()]
        c = [int(e) for e in inp().split()]
        A.append(a)
        B.append(b)
        C.append(c)
    print(solve(N, M, A, B, C))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
r=[0]+[10**9]*(2**N-1)
for i in range(M):
    a,_=map(int,input().split())
    c=map(int,input().split())
    x=0
    for e in c:
        x+=1<<(e-1)
    for j in range(2**N):
        r[x|j]=min(r[x|j],r[j]+a)
print(r[-1] if r[-1]<10**9 else -1)

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    N, M = map(int, input().split())
    key_data = list()
    INF = 1001001001
    for i in range(M):
        a, b = map(int, input().split())
        c = sum(1 << (ci - 1) for ci in map(int, input().split()))
        key_data.append([a, c])

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

    for j in range(2**N):
        for i in range(M):
            k = j | key_data[i][1]
            cost = dp[j] + key_data[i][0]
            if dp[k] > cost:
                dp[k] = cost

    if dp[2**N - 1] == INF:
        print('-1')
    else:
        print(dp[2**N - 1])

Submission status: Accepted

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

keys = [None] * m
dlen = 2**n
inf = float("inf")
dp = [inf] * dlen

for i in range(m):
    a, _ = map(int, input().split())
    c = 0
    for num in map(int, input().split()):
        c += 2 ** (num - 1)
    
    keys[i] = (a, c)

for price, key in keys:
    for i in range(dlen):
        if dp[i] == inf: continue
        new = key | i
        dp[new] = min(dp[new], dp[i] + price)
    
    dp[key] = min(dp[key], price)

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

Submission status: Accepted

Solution code:
#import hoge
##################################################################
Input1 = [input() for i in range(1)]
N,M = list(map(int,Input1[0].split()))
Input2 = [input() for i in range(M*2)]
A,B,C = [],[],[]
for i in range(M):
    a,b = list(map(int,Input2[i*2].split()))
    A.append(a)
    B.append(b)
    c = list(map(int,Input2[i*2+1].split()))
    C.append(c)

d = []
for c in C:
    r = 0
    for j in c:
        r |= 2**(j-1)
    d.append(r)

dp = [1000000000]*2**N
dp[0] = 0
for i in range(2**N): #あらゆる開け方をsimする
    for j in range(M): #すべての鍵について確認する
        temp = d[j] | i #今回の開け方についてさらに鍵jを使ったとき
        cost = dp[i] + A[j]
        if dp[temp] > cost: #costが既知の開け方よりも安ければ
            dp[temp] = cost #それを新しい開け方とする

if dp[-1] == 1000000000:
    print(-1)
else:
    print(dp[-1])
#print([format(dd, 'b') for dd in d])
    
#print(' '.join(map(str,B)))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
INF = 10**8
N_dp = 2**N
DP = [INF] * (N_dp)
DP[0] = 0

for i in range(M):
    a,b = map(int,input().split())
    C = [int(i) for i in input().split()]
    c_bit = sum(2**(c-1) for c in C)
    for i in range(N_dp):
        DP[c_bit | i] = DP[i] + a if(DP[i]+a < DP[c_bit | i]) else DP[c_bit | i]
if(DP[-1] == INF):
    DP[-1] = -1
print(DP[-1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc142/submissions/7753443
 
N,M = map(int,input().split())
 
lis = [float("inf")] * (2 ** N)
lis[0] = 0
 
for i in range(M):
 
    a,b = map(int,input().split())
 
    c = list(map(int,input().split()))
 
    num = 0
    for j in c:
        num += 2 ** (j-1)
 
    nlis = lis.copy()
    for j in range(2 ** N):
 
        if lis[j | num] > nlis[j] + a:
            lis[j | num] = nlis[j] + a     
 
#print (lis)
if lis[2 ** N -1] == float("inf"):
    print (-1)
 
else:
    print (lis[2 ** N - 1])

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
 
n, m = map(int, input().split())
value = []
for i in range(m):
    A, B = map(int, input().split())
    c = sum(1<<(ci-1) for ci in map(int, input().split()))
    value.append([A, c])
    
dp = [100100100] * (1<<n)
dp[0] = 0
for s in range(1<<n):
    for i in range(m):
        t = s | value[i][1]
        cost = dp[s] + value[i][0]
        if dp[t] > cost:
            dp[t] = cost
        
if dp[(1<<n)-1] == 100100100:
    print(-1)
else:
    print(dp[(1<<n)-1])

Submission status: Accepted

Solution code:
#解説放送見てからの書き直し
import sys
import os
INF = 10**12
ans = INF
N, M = map(int,input().split())
A = [0 for _ in range(M)]
B = [0 for _ in range(M)]
C = []
for i in range(M):
    a, b = map(int,input().split())
    A[i] = a  #鍵の金額
    B[i] = b  #開けられる宝箱の種類数
    tmp = list((map(int,input().split())))
    s = 0
    for j in range(b):
        t = tmp.pop(0)-1
        s |= 1 << t
    C.append(s)
    
dp = [INF]*(1<<N) #2^N
dp[0] = 0 #0 = 0b0000の時、スコアは0（まだ1つも鍵を購入してないので）

for s in range(1<<N): #1<<Nは2^N。つまりどの宝箱が開くかの全ての状態
    for j in range(M): # 全ての鍵について見ていく
        t = s | C[j] # 論理和。sには現在どの宝箱が開けられるかの状態、
                     # C[j]にはその新たな鍵が開ける宝箱。
                     # その論理和はこれまでの鍵と新たな鍵でどの宝箱が開けられるか
        cost = dp[s] + A[j] # その鍵を買った時のコスト
        dp[t] = min(dp[t],cost) #新たな宝箱の状態について、コストがより低くなるようなら保存する。
ans = dp[-1] #dp[-1]、つまり0b1111。宝箱が全て開けられる状態。
if ans == INF: #もし0b1111がINFのまま（最初から変わってない）ということはそこにたどり着けなかったということ。
               #つまり、全ての鍵を使っても宝箱を開けられなかった。
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
#show_flg=True

n,m=MI()
t=1<<n
key=[]
for i in range(m):
    a,b=MI()
    c=0
    for j in LI_():
        c+=1<<j
    key.append((a,c))
inf=float('inf')
dp=[[inf]*(m+1) for _ in range(t)]
#dp[stat][m] # min value using up to m and open stat
dp[0][0]=0

for j in range(1,m+1):
    for i in range(t):
        cost,ck=key[j-1]
        show(i,j,'|',dp[ck|i][j],min(dp[ck|i][j-1],dp[i][j-1]+cost))
        dp[ck|i][j]=min(dp[ck|i][j],dp[ck|i][j-1],dp[i][j-1]+cost)
        dp[i][j]=min(dp[i][j],dp[i][j-1])
        
for i in dp:
    show(*i)

ans=dp[t-1][m] if dp[t-1][m]!=inf else -1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
inf = 10**8+1
dp = [inf]*(2**n)
dp[-1] = 0
for _ in range(m):
    a, b = map(int, input().split())
    c = sum(2**(i-1) for i in map(int, input().split()))
    for j in range(len(dp)):
        dp[j] = min(dp[j], a+dp[j|c])
if dp[0] == inf:
    print(-1)
else:
    print(dp[0])

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    k = []
    for i in range(m):
        a, _ = map(int, input().split())
        c = sum([1<<i for i in map(lambda x: int(x)-1, input().split())])
        k.append((a, c))
    dp = [float("inf")]*(1<<n)
    dp[0] = 0
    for i in range(1<<n):
        for ki in range(m):
            c = dp[i] + k[ki][0]
            t = i | k[ki][1]
            dp[t] = min(dp[t], c)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
N2 = 2**N
# 各状態のコストが入る関数
# 10**8+1にしているのはmaxコスト10**5の鍵が最大10**3個ある（＝10**8）のでそれより1高くしている
# 最終的にX[-1]が10**8+1なら-1を出力すれば良い
X = [10**8+1]*N2
X[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    
    # 1, 2 → 11、2　→ 10　みたいなやつ作る
    k = sum(1<<(c-1) for c in C)
    for j in range(N2):
        # 各状態からこの鍵を追加したときに行ける状態(j|k)のコストが小さくなればそれを採用
        if X[j|k] > X[j] + a:
            X[j|k] = X[j] + a

ans = X[-1]
if ans >= 10**8+1:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
def calc(N, M, a, c):
    for j in range(N):
        u = sum([c[i][j] for i in range(M)])
        if u == 0:
            return -1
    inf = 10 ** 7 + 1
    L = 2 ** N
    dp = [inf for _ in range(L)]
    dp[0] = 0
    C = [sum([_c[i] * 2 ** i for i in range(N)]) for _c in c]
    for _ in range(M):
        dp_x = list(dp)
        for i in range(M):
            for j in range(L):
                if dp[j] == inf:
                    continue
                dp_x[j | C[i]] = min(dp_x[j | C[i]], dp[j] + a[i])
            dp = dp_x
        if dp[L - 1] < inf:
            return dp[L - 1]
    return -1


(N, M) = tuple([int(s) for s in input().split(' ')])
a = [0 for _ in range(M)]
c = [[0 for _ in range(N)] for _ in range(M)]
for i in range(M):
    (_a, _b) = tuple([int(s) for s in input().split(' ')])
    a[i] = _a
    for _c in [int(s) for s in input().split(' ')]:
        c[i][_c - 1] = 1
print(calc(N, M, a, c))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
 
a = []
b = []
c = {}
for i in range(m):
    _a, _b = list(map(int, input().split()))
    a.append(_a)
    b.append(_b)
    c[i] = list(map(int, input().split()))
    
inf = int(10e+6)
 
dp = [inf]*(2**n)
dp[0] = 0
 
def rec(dp_i, cost):
    if dp[dp_i] > cost:
        dp[dp_i] = cost
        
    return
 
for _ci, _cv in c.items():
    now = 0
    for _v in _cv:
        now |= 1 << _v-1
    
    for bits in range(1 << n):
        rec(bits|now, dp[bits] + a[_ci])
 
        
if dp[(1 << n) - 1] == inf:
    print(-1)
else:
    print(dp[(1 << n) - 1])

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
A = []
C = []

for i in range(M):
    A.append(int(input().split()[0]))
    C.append(list(map(int,input().split())))


inf = 1000000000
dp = [inf for _ in range(2**N)]
dp[0] = 0

for i in range(M):
    cost = A[i]
    candidate = C[i]
    mask = 0
    for c in candidate:
        mask += 1 << (c-1)
    for j in range(2**N):
        if dp[j|mask] > dp[j] + cost:
            dp[j|mask] = dp[j] + cost

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

Submission status: Accepted

Solution code:

def main():
    N, M = map(int, input().split())
    inf = int(1e10)
    dp = [inf] * (1 << N) #1をNだけシフトする 2**B
    #鍵をビットで表す　dp[i]は鍵の状態iにできる最小費用を
    dp[0] = 0
    bits = set()
    bits.add(0)
    for i in range(M):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        # cを状態keyに変換
        key = 0
        for t in c:
            key += 1 << (t - 1)
        # bits内のbitとkeyのORを更新
        # 更新したbitはbitsに追加
        add_bits = set()
        for bit in bits:
            tmp = bit | key
            if dp[bit] + a < dp[tmp]:
                dp[tmp] = dp[bit] + a
                add_bits.add(tmp)
        bits |= add_bits
    
    if dp[(1 << N) - 1] == inf:
        print(-1)
    else:
        print(dp[(1 << N) - 1])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]
    check={}

    for i in range(M):
        mon,_ =two_int()
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        
        if sums in check:
            if check[sums] > mon:
                check[sums]=mon
        else:
            check[sums]=mon
            
    for k,v in check.items():
        key_list.append(v)
        treasures.append(k)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp[0]=0
    M=len(key_list)

    for i in range(max_index-1):
        for j in range(M):
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()

Submission status: Accepted

Solution code:
# 解説放送の解法

INF = 1001001001

N, M = map(int, input().split())
key = []
for i in range(M):
    a, b = map(int, input().split())
    f = 0
    for c in list(map(int, input().split())):
        c -= 1
        # f は開けられる宝箱の集合
        f |= 1 << c
    key.append((f, a))

dp = [INF] * (1 << N)
dp[0] = 0

# 遷移元の状態
for f in range(1 << N):
    # 鍵を全て試す
    for i in range(M):
        # 遷移先の状態
        t = f | key[i][0]
        # 遷移先のコスト = 遷移元のコスト + 鍵の値段
        cost = dp[f] + key[i][1]
        # 小さい方に更新
        dp[t] = min(dp[t], cost)

ans = dp[-1]
if ans == INF:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
# 解説放送の解法

INF = 1001001001

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

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

ans = dp[-1]
if ans == INF:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dp = [10**9] * (2**n)
dp[0] = 0
for i in range(m):
    a, _ = map(int, input().split())
    # [1, 2], [1, 3]などが入る
    c = list(map(int, input().split()))
    t = 0
    # リストに何が入っているかを2進数で表す
    # c = [1, 2] なら t = 3(011)
    # c = [1, 3] なら t = 5(101)
    for x in c:
        t |= 1 << (x-1)
    for b in range(2**n):
        # これまでに確定したdb[b]とdb[t]の論理和で変える鍵の価格より、
        # これまでのdb[b]と今回の価格を足したものの方が安ければ今回の価格で上書きする
        dp[b|t] = min(dp[b|t], dp[b]+a)
if dp[-1] > 10**8:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
from itertools import combinations

# 全ての部分集合の列挙
def subset_family(items, length):
    subsets = []
    for i in range(length + 1):
        for c in combinations(items, i):
            subsets.append(c)
    return subsets


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

dp = [[float('inf')] * (2 ** N) for _ in range(M + 1)]
for i in range(M + 1):
    dp[i][0] = 0
"""
dp[i][j] = (i + 1 番目以降の鍵は購入せずに状態を j にする為に必要な最小費用)
部分集合族はビットで管理すれば良い(0 <= j <= 2**N-1)
"""

for i in range(1, M + 1):
    dp[i] = dp[i - 1]
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    for j in range(2 ** N):
        """
        DPは送る方向に考えるか受け取る方向に考えるかの２通りのやり方がある
        今回は受け取る方は難しいので送る方で考える
        またjは昇順に考えると偶然うまくDPの状態が順番に確定していく
        """
        """
        以下のようにcで開けられる箱の部分集合全てを考えても良いが、
        結局ほしいのはdp[M][2 ** N - 1]の右端の値なので、中間状態は吹っ飛ばして良い。
        for subset in subset_family(c, b):
            val = 0
            for num in subset:
                val += 2 ** (num - 1)

            if j | val < 2 ** N:
                dp[i][j | val] = min(dp[i - 1][j] + a, dp[i - 1][j | val])
        """
        val = 0
        for num in c:
            val += 2 ** (num - 1)
        dp[i][j | val] = min(dp[i - 1][j] + a, dp[i - 1][j | val])
    #print('dp[{}]={}'.format(i, dp[i]))

ans = dp[M][2 ** N - 1]
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split(" "))
class _const:
    def __init__(self):
        self.__INT_MAX = 0x7fffffff

    @property
    def INT_MAX(self):
        return self.__INT_MAX

const=_const()

dp=[ const.INT_MAX for i in range((1<<N)) ]
dp[0]=0
for i in range(M):
    val,T=map(int,input().split(" "))
    r=list( map(int,input().split(" ")) )
    
    now = 0
    for it in r:
        now |= (1<<(it-1))
    for bits in range((1<<N)):
        dp[bits | now] = min(dp[ bits | now ],dp[bits]+val)


if dp[-1]==const.INT_MAX:
    print("-1")
else:
    print(dp[-1])

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    INF = int(1e10)
    dp = [INF] * (1 << N)
    dp[0] = 0
    bits = set()
    bits.add(0)
    for i in range(M):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        # cを状態keyに変換
        key = 0
        for t in c:
            key += 1 << (t - 1)
        # bits内のbitとkeyのORを更新
        # 更新したbitはbitsに追加
        add_bits = set()
        for bit in bits:
            tmp = bit | key
            if dp[bit] + a < dp[tmp]:
                dp[tmp] = dp[bit] + a
                add_bits.add(tmp)
        bits |= add_bits
    
    if dp[(1 << N) - 1] == INF:
        print(-1)
    else:
        print(dp[(1 << N) - 1])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    INF = int(1e10)
    dp = [INF] * (1 << N)
    dp[0] = 0
    bits = set()
    bits.add(0)
    for i in range(M):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        key = 0
        for t in c:
            key += 1 << (t - 1)
        add_bits = set()
        for bit in bits:
            tmp = bit | key
            if dp[bit] + a < dp[tmp]:
                dp[tmp] = dp[bit] + a
                add_bits.add(tmp)
        bits |= add_bits
    
    if dp[(1 << N) - 1] == INF:
        print(-1)
    else:
        print(dp[(1 << N) - 1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 所持している鍵の集合をbitで表現する
#　鍵の集合を表す2進数が少なくなる方向に遷移することはないから，for文for文でかける

N, M = map(int, input().split())
status_money = [float('inf')] * (1 << N)

# 初期状態からの遷移を記録
for _ in range(M) :
    a, b = map(int, input().split())
    C = 0
    for c in input().split() :
        C |= (1 << (int(c) - 1))
    status_money[C] = min(status_money[C], a)
    
# ある状態とある状態の組合せを全部取る
for c in range(1 << N):
    # どんな鍵の組合せでも到達できない宝箱の組合せがあるかもしれない
    if status_money[c] == float('inf'):
        continue
    for d in range(1 << N):
        # c と d の論理和をとって新しく生成される状態 e を考える
        e = c | d
        # eにあらかじめ格納されている最小コストと，今生成したコストとのminをとる
        status_money[e] = min(status_money[c] + status_money[d], status_money[e])

# そもそも到達できない場合の処理を記述       
if status_money[-1] == float('inf'):
    print(-1)
else:
    print(status_money[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def main():
    N, M = map(int, input().split())
    cd = {}
    FAIL = (10 ** 3) * (10 ** 5) + 1
    for _ in range(M):
        ai, _ = map(int, input().split())
        ci = sum(1 << (int(i) - 1) for i in input().split())
        keys = list(cd.keys())
        for i in keys:
            cd[i | ci] = min(cd.get(i | ci, FAIL), cd[i] + ai)
        cd[ci] = min(cd.get(ci, FAIL), ai)
    print(cd.get((1 << N) - 1, -1))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
f,*L=open(0).readlines()
n,m=map(int,f.split())
t=[(int(a.split()[0]),list(map(int,b.split()))) for a,b in zip(*[iter(L)]*2)]
K=[]
for a,C in t:
  r=0
  for c in C:
    r|=2**(c-1)
  K.append((a,r))
INF=float('inf')
dp=[INF]*(2**n)
dp[0]=0
for g in range(2**n):
  for a,c in K:
    if dp[g|c]>dp[g]+a:
      dp[g|c]=dp[g]+a
print(-1 if dp[-1]==INF else dp[-1])

Submission status: Accepted

Solution code:
#n,m=0,0
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( )))
    C2 = 0
    for i in C:
        C2 += 2**(i-1)
    a.append(A)
    c.append(C2)

#print(a)
#print(c)
#dp = [[10**9 for j in range(2**n)] for i in range(m)]
dp = [10**9 for j in range(2**n)]
dp[0] = 0
#for i in range(m):
#    dp[i][0] = 0
#print(dp)
##ちょうど開く箱がどれか、で状態を追う。
##指定した箱以外は開いていない。

#直前以外使わないのだが
#c[i]まで使ったdpとc[i-1]までしか使っていないdpが混在していいのか
#↑試しに消してみた
for i in range(m):
    for j in range(2**n):
        #dp[i][j] = min(dp[i][j],dp[i-1][j])
        dp[j|c[i]] = min(dp[j|c[i]],dp[j] + a[i])

        #dp[i][j|c[i]] = min(dp[i-1][j|c[i]],dp[i-1][j] + a[i])
        #print(dp[i][j|c[i]],end = " ")
    #print(dp[i],dp[i][c[i]])
#print(dp)
#print(dp[m-1][2**n-1])
if dp[2**n-1]<10**9-1:
    print(dp[2**n-1])
else:
    print(-1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
N2 = 2**N
INF = float("inf")
X = [INF]*N2
X[0] = 0

for i in range(M):
  a, b = map(int, input().split())
  C = list(map(int, input().split()))
  
  k = sum(1<<(c-1) for c in C)
    
  for j in range(N2):
    if X[j|k] > X[j] + a:
      X[j|k] = X[j] + a

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

Submission status: Accepted

Solution code:
def read_key():
    a, _ = map(int, input().split())
    m = 0
    for c in map(int, input().split()):
        m |= 1 << (c - 1)
    return (a, m)


INF = float('inf')

N, M = map(int, input().split())
keys = [read_key() for _ in range(M)]

dp = [INF] * (1 << N)

dp[0] = 0
for i in range(M):
    a, m = keys[i]
    for j in range((1 << N)-1, -1, -1):
        if dp[j] == INF:
            continue
        if dp[j] + a < dp[j | m]:
            dp[j | m] = dp[j] + a

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

Submission status: Accepted

Solution code:
def read_key():
    a, _ = map(int, input().split())
    m = 0
    for c in map(int, input().split()):
        m |= 1 << (c - 1)
    return (a, m)


def main():
    INF = float('inf')

    N, M = map(int, input().split())
    keys = [read_key() for _ in range(M)]

    dp = [[INF] * (1 << N) for _ in range(M + 1)]

    dp[0][0] = 0
    for i in range(M):
        a, m = keys[i]
        dpi = dp[i]
        dpi1 = dp[i + 1]
        for j in range(1 << N):
            if dpi[j] == INF:
                continue
            if dpi[j] + a < dpi1[j | m]:
                dpi1[j | m] = dpi[j] + a
            if dpi[j] < dpi1[j]:
                dpi1[j] = dpi[j]

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


main()

Submission status: Accepted

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


def main():

    INF = 10 ** 7
    n, m = map(int, input().split())
    state_num = 1 << n
    key = []
    for i in range(m):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        bt = 0
        for e in c:
            bt |= 1 << (e - 1)
        key.append((bt, a))

    dp = [INF for _ in range(state_num)]
    dp[0] = 0

    for i in range(state_num):
        for j in range(m):
            ks, kc = key[j]
            state = i | ks
            cost = dp[i] + kc
            dp[state] = min(dp[state], cost)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC142E - Get Everything
import sys
input = sys.stdin.readline

def main():
    chmin = lambda x, y: x if x <= y else y
    N, M = map(int, input().split())
    p, INF = 1 << N, 1 << 60
    # bitDP of minimum cost to buy the subset of items represented by binary
    dp = [INF] * p
    dp[0] = 0
    for _ in range(M):
        a, _ = map(int, input().split())
        x = sum(1 << (i - 1) for i in map(int, input().split()))
        for y in range(p):
            dp[x | y] = chmin(dp[x | y], dp[y] + a)
    ans = dp[-1] if dp[-1] != INF else -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC142E - Get Everything
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    p, INF = 1 << N, 1 << 60
    # bitDP of minimum cost to buy the subset of items represented by binary
    dp = [INF] * p
    dp[0] = 0
    for _ in range(M):
        a, _ = map(int, input().split())
        x = sum(1 << (i - 1) for i in map(int, input().split()))
        for y in range(p):
            dp[x | y] = min(dp[x | y], dp[y] + a)
    ans = dp[-1] if dp[-1] != INF else -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC142E - Get Everything
def main():
    N, M = map(int, input().split())
    p, INF = 1 << N, 1 << 60
    # bitDP of minimum cost to buy the subset of items represented by a binary
    dp = [INF] * p
    dp[0] = 0
    for _ in range(M):
        a, _ = map(int, input().split())
        x = sum(1 << (i - 1) for i in map(int, input().split()))
        for y in range(p):
            dp[x | y] = min(dp[x | y], dp[y] + a)
    ans = dp[-1] if dp[-1] != INF else -1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

# INF = float("inf")
INF = 10 ** 8
dp = [INF] * ((1<<n) + 1)
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c = sum(1<<(ci-1) for ci in map(int, input().split()))

    for j in range(1<<n):
        # if dp[j] + a < dp[j | c]:
        #     dp[j | c] = dp[j] + a
        jc = j | c
        dp[jc] = min(dp[j] + a, dp[jc])

if dp[(1<<n) - 1] == INF:
    ans = -1
else:
    ans = dp[(1<<n) - 1]

print(ans)

Submission status: Accepted

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

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

# INF = float("inf")
INF = 10 ** 8
dp = [INF] * ((1<<n) + 1)
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c = sum(1<<(ci-1) for ci in map(int, input().split()))

    for j in range(1<<n):
        # if dp[j] + a < dp[j | c]:
        #     dp[j | c] = dp[j] + a
        dp[j | c] = min(dp[j] + a, dp[j | c])

if dp[(1<<n) - 1] == INF:
    ans = -1
else:
    ans = dp[(1<<n) - 1]

print(ans)

Submission status: Accepted

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

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

# INF = float("inf")
INF = 10 ** 8
dp = [INF] * ((1<<n) + 1)
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c = sum(1<<(ci-1) for ci in map(int, input().split()))

    for j in range(1<<n):
        if dp[j] + a < dp[j | c]:
            dp[j | c] = dp[j] + a
        # dp[j | c] = min(dp[j] + a, dp[j | c])


if dp[(1<<n) - 1] == INF:
    ans = -1
else:
    ans = dp[(1<<n) - 1]

print(ans)