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:
N, M = map(int, input().split())
newcount = [float('inf') for _ in range(2**N)]
newcount[0] = 0

for k in range(M):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  bit = 0
  for k in range(b):
    bit += 2**(c[k]-1)
  count = tuple(newcount)
  for k in range(2**N):
    now = bit|k
    newcount[now] = min(newcount[now], a+count[k])
count = newcount
if count[-1] < 10**6:
  print(count[-1])
else:
  print(-1)

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
dp = [float("inf")]*(2**N)
dp[0] = 0
for i in range(1, M+1):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    d = 0
    for j  in range(1, N+1):
        if j in c:
            d += 2**(j-1)
    for j in range(2**N):
        dp[j | d] = min(dp[j | d], dp[j] + a)
print(dp[-1] if dp[-1] != float("inf") else -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()))
    cnt=0
    for j in c:
        cnt+=2**(j-1)
    
    for j in range(2**n):
        dp[j|cnt]=min(dp[j|cnt],dp[j]+a)


if dp[2**n-1]>10**10:
    print(-1)

else:
    print(dp[2**n-1])

Submission status: Accepted

Solution code:
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    N, M = read_ints()
    # key to cover
    cover = [0]*M
    # key to cost
    costs = [0]*M
    INF = 10**9+1
    for i in range(M):
        a, b = read_ints()
        costs[i] = a
        for c in read_ints():
            cover[i] |= 1<<(c-1)
    # mask to cost
    mask_to_cost = [INF]*(1<<N)
    mask_to_cost[0] = 0
    for mask in range(1<<N):
        for i in range(M):
            mask_to_cost[cover[i]|mask] = min(mask_to_cost[cover[i]|mask], mask_to_cost[mask]+costs[i])
    return mask_to_cost[(1<<N)-1] if mask_to_cost[(1<<N)-1] != INF else -1


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, M, ABCi):
    inf = 10 ** 5 * 12 * 2
    for i in range(M):
        C = ABCi[i][2]
        ABCi[i][2] = sum([2 ** (c - 1) for c in C])
    # dp[i番目までのカギだけ購入したときに][bin(j)の宝箱が開けられる最小金額]
    dp = [[inf] * (2 ** N) for _ in range(M + 1)]
    dp[0][0] = 0
    for i in range(1, M + 1):
        for j in range(2 ** N):
            a, b, c = ABCi[i - 1]
            dp[i][j] = min(dp[i - 1][(c & j) ^ j] + a, dp[i - 1][j])
    ans = min([x[2 ** N - 1] for x in dp])
    if ans == inf:
        ans = -1
    print(ans)


if __name__ == '__main__':
    N, M = map(int, input().split())
    ABCi = [
        [int(i) for i in input().split()] + [[int(i) for i in input().split()]]
        for _ in range(M)]
    solve(N, M, ABCi)

    # # test
    # from random import randint, sample
    # from func import random_str
    # N, M = 12, 10 ** 3
    # tmp = [i for i in range(1, N + 1)]
    # ABCi = [[randint(1, 10 ** 5), randint(1, N)] for _ in range(M)]
    # print(ABCi)
    # for i in range(M):
    #     ABCi[i].append(sample(tmp, ABCi[i][1]))
    # solve(N, M, ABCi)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
#D流用したので文字滅茶苦茶
N,M=map(int,input().split())

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

for _ in range(M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    
    can_open=sum([2**(c[i]-1) for i in range(len(c))])
    
    for i in range(len(dp))[::-1]:
        if dp[i]!=10**10 and i|can_open<2**N:
            dp[i|can_open]=min(dp[i]+a,dp[i|can_open])


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

Submission status: Accepted

Solution code:
def main():
  n,m=map(int,input().split())
  inf=10**9
  dp=[inf]*(1<<n)
  dp[0]=0
  for i in range(m):
    a,b=map(int,input().split())
    t=sum([1<<(int(x)-1) for x in input().split()])
    for s in range(1<<n):
      dp[t|s]=dp[t|s] if dp[t|s]<=dp[s]+a else dp[s]+a
  print(-1 if dp[-1]==inf else dp[-1])
  
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def min(a,b):
  return a if a<=b else b


def main():
  n,m=map(int,input().split())
  inf=10**9
  cost=[0]*m
  dp=[inf]*(1<<n)
  dp[0]=0
  for i in range(m):
    a,b=map(int,input().split())
    t=sum([1<<(int(x)-1) for x in input().split()])
    for s in range(1<<n):
      dp[t|s]=min(dp[t|s], dp[s]+a)
  print(-1 if dp[-1]==inf else dp[-1])
  
  
if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = []
b = []
c = []
checker = [0]*n
for _ in range(m):
    ai, bi = map(int, input().split())
    ci = list(map(int, input().split()))
    ci_int = 0
    for hako in ci:
        hako -= 1
        ci_int += 2**hako
        if checker[hako] == 0:
            checker[hako] = 1
    a.append(ai)
    b.append(bi)
    c.append(ci_int)
#print(a)
#print(b)
#print(c)
if sum(checker) != n:
    print(-1)
    exit()

dp = [[float("inf")]*(2**n) for _ in range(m+1)]
#dp[i][S]はi番目までのカギをいくつか使ってSになるようなコストの最小値
#Sは2進数で表現できる。例）１と３の箱が開けられる状態->0b101
dp[0][0] = 0
for i in range(m):
    for s in range(2**n):
        # i番目のカギを使用しない場合
        dp[i+1][s] = min(dp[i+1][s], dp[i][s])
        # 使用する場合
        dp[i+1][s | c[i]] = min(dp[i+1][s|c[i]], dp[i][s] + a[i])
print(dp[m][2**n-1])

Submission status: Accepted

Solution code:
import copy
N, M = map(int, input().split())
key = [0] * M
bin_max = (2 ** N) 
dp = [[float('inf')] * (bin_max) ]
for i in range(M):
  a, _ =  map(int, input().split())
  c = list(map(int, input().split()))
  temp = 0
  for j in c:
    temp += (1 << (j-1))
  key[i] = ([a,temp])
  
for i in range(0,M):
  b = key[i][1]
  value = key[i][0]
  dp_low = copy.copy(dp[i])
  for j in range(1,bin_max):
    if j & b == j and dp_low[j] > value:
      dp_low[j] = value
    if dp_low[j] != float('inf'):
      next_b = j | b
      next= dp_low[j] + value
      if dp_low[next_b] > next:
        dp_low[next_b] = next
  dp.append(dp_low)
ans = -1 if dp[M-1][bin_max - 1] == float('inf') else dp[M-1][bin_max - 1]
print(ans)

Submission status: Accepted

Solution code:
def main():
  n,m=map(int,input().split())
  inf=10**9
  dp=[inf]*(1<<n)
  dp[0]=0
  
  #cost=[inf for i in range(m)]
  for i in range(m):
    a,b=map(int,input().split())
    c=[1<<(int(x)-1) for x in input().split()]
    t=sum(c)
    #cost[i]=[s,a]
    for s in range(1<<n):
      if dp[t|s]>dp[s]+a:
        dp[t|s]=dp[s]+a
      #dp[t|s]=min(dp[t|s], dp[s]+a)
    
  #print(cost)
  """
  dp=[inf]*(1<<n)
  dp[0]=0
  for s in range(1<<n):
    for bit,c in cost:
      dp[s|bit]=min(dp[s|bit], dp[s]+c)
  #print(dp)
  """
  #print(dp)
  print(-1 if dp[-1]==inf else dp[-1])

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  n,m=map(int,input().split())
  inf=10**9
  dp=[inf]*(1<<n)
  dp[0]=0
  
  #cost=[inf for i in range(m)]
  for i in range(m):
    a,b=map(int,input().split())
    c=[1<<(int(x)-1) for x in input().split()]
    t=sum(c)
    #cost[i]=[s,a]
    for s in range(1<<n):
      dp[t|s]=min(dp[t|s], dp[s]+a)
    
  #print(cost)
  """
  dp=[inf]*(1<<n)
  dp[0]=0
  for s in range(1<<n):
    for bit,c in cost:
      dp[s|bit]=min(dp[s|bit], dp[s]+c)
  #print(dp)
  """
  #print(dp)
  print(-1 if dp[-1]==inf else dp[-1])

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  n,m=map(int,input().split())
  inf=10**9
  dp=[inf]*(1<<n)
  dp[0]=0
  
  #cost=[inf for i in range(m)]
  for i in range(m):
    a,b=map(int,input().split())
    c=[int(x)-1 for x in input().split()]
    t=0
    for j in c:
      t|=1<<j
    #cost[i]=[s,a]
    for s in range(1<<n):
      dp[t|s]=min(dp[t|s], dp[s]+a)
    
  #print(cost)
  """
  dp=[inf]*(1<<n)
  dp[0]=0
  for s in range(1<<n):
    for bit,c in cost:
      dp[s|bit]=min(dp[s|bit], dp[s]+c)
  #print(dp)
  """
  #print(dp)
  print(-1 if dp[-1]==inf else dp[-1])

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
def main():
  n,m=map(int,input().split())
  inf=10**9
  cost=[inf for i in range(m)]
  for i in range(m):
    a,b=map(int,input().split())
    c=[int(x)-1 for x in input().split()]
    s=0
    for j in c:
      s|=1<<j
    cost[i]=[s,a]
  #print(cost)

  dp=[inf]*(1<<n)
  dp[0]=0
  for s in range(1<<n):
    for bit,c in cost:
      dp[s|bit]=min(dp[s|bit], dp[s]+c)
  #print(dp)
  print(-1 if dp[-1]==inf else dp[-1])

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
inf=10**9
cost=[inf for i in range(m)]
for i in range(m):
  a,b=map(int,input().split())
  c=[int(x)-1 for x in input().split()]
  s=0
  for j in c:
    s|=1<<j
  cost[i]=[s,a]
#print(cost)

dp=[inf]*(1<<n)
dp[0]=0
for s in range(1<<n):
  for bit,c in cost:
    dp[s|bit]=min(dp[s|bit], dp[s]+c)
#print(dp)
print(-1 if dp[-1]==inf else dp[-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dp = [float("inf") for i in range(2 ** n)]
dp[0] = 0

for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    num = 0
    for j in range(b):
        num += 2 ** (c[j] - 1)
    for k in range(2 ** n):
        dp[k | num] = min(dp[k | num], dp[k] + a)
if dp[2 ** n - 1] == float("inf"):
    print(-1)
else:
    print(dp[2 ** n - 1])

Submission status: Accepted

Solution code:
import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


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

    dp = [10 ** 9] * pow(2,N)
    dp[0] = 0

    for j in range(M):
        a, b = map(int, input().split())
        c = sum([pow(2, int(i) - 1) for i in input().split()])
        for i in range(pow(2,N)):
            dp[i | c] = min(dp[i | c], dp[i] + a)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
key=[]
for _ in range(m):
  a,b=map(int,input().split())
  c=list(map(int,input().split()))
  bi=0
  for i in c:
    bi+=1<<(i-1)
  key.append([a,bi])
#print(key)

INF=2**24
dp=[INF]*(1<<n)
dp[0]=0
for k in key:
  for b in range(1<<n):
    dp[b|k[1]]=min(dp[b|k[1]],dp[b]+k[0])
    #print(b,k[1],b|k[1],dp)
    
print(-1 if dp[-1]==INF else dp[-1])

Submission status: Accepted

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

dp = [[float('inf')] * (1<<n) for _ in range(m+1)]
dp[0][0] = 0
for i in range(m):
    money, value = key[i]
    for j in range(1<<n):
        dp[i+1][j|value] = min(dp[i+1][j|value], dp[i][j] + money)
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

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

Submission status: Accepted

Solution code:
import math

N, M = map(int, input().split())
dp = [math.inf] * pow(2, N)  # (どの宝箱をあけたかのbit)=>現時点の最小値
dp[0] = 0
for _ in range(M):
    a, b = map(int, input().split())
    c = sum([pow(2, int(i)-1) for i in input().split()])
    for i in range(pow(2, N)):
        dp[i | c] = min(dp[i | c], dp[i] + a)
print(dp[-1] if dp[-1]!=math.inf else -1)

Submission status: Accepted

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

INF = float("inf")
# bitで表される状態を満たすための最小コスト
# ex. N=2
# [00]=1つも開かない, [01]=1だけ開く, [10]=2だけ開く, [11]=1,2の両方開く
dp = [INF] * (2**N)
# 1つも開かない状態はコスト0で実現される
dp[0] = 0

for i in range(1, M + 1):
    a, b = map(int, input().split())

    # ex.
    # c = [1] -> tmp = 01(2) = 1
    # c = [2] -> tmp = 10(2) = 2
    # c = [1,2] -> tmp = 11(2) = 3
    tmp = 0
    for c in list(map(int, input().split())):
        tmp += 1 << (c - 1)

    # target = ある状態(j)に対して、鍵(tmp)を使った後の状態
    # ex.
    # 状態00に鍵01を使う -> 結果は01(1が新しく開く)
    # 状態01に鍵01を使う -> 結果は01（変わらない）
    # 状態10に鍵01を使う -> 結果は11（１が新しく開く）
    # 状態11に鍵01を使う -> 結果は11（１が新しく開く）
    for j in range(2**N):
        # | = 論理和(OR)
        target = j | tmp
        # 状態jから鍵のコストaを支払ってtargetに遷移 or そのまま
        dp[target] = min(dp[j] + a, dp[target])

# 更新されていない場合、全て開けることは実現できない
if dp[2**N - 1] == INF:
    print(-1)
# 更新されている場合、全て開けることが可能
else:
    print(dp[2**N - 1])

Submission status: Accepted

Solution code:
import math

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

keys = []

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

dp = [math.inf]*(1 << N)

dp[0] = 0

for i in range(M):
    for j in range(1 << N):
        dp[j | keys[i][1]] = min(dp[j | keys[i][1]], dp[j] + keys[i][0])

if dp[-1] == math.inf:
    dp[-1] = -1

print(dp[-1])

Submission status: Accepted

Solution code:

def resolve():
    INF = 10 ** 18
    N, M = map(int, input().split())

    Box_key = []
    for i in range(M):
        a, b = map(int, input().split())
        C = list(map(int, input().split()))
        s = sum(1 << (c - 1) for c in C)
        Box_key.append((s, a))

    # dp[i]: 集合iの宝箱を開ける最小コスト
    dp = [INF] * (1 << N)
    dp[0] = 0

    for s in range(1 << N):
        for i in range(M):
            ns = s | Box_key[i][0]
            cost = dp[s] + Box_key[i][1]
            dp[ns] = min(dp[ns], cost)

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
k=[]
for i in range(m):
  a,b=map(int,input().split())
  c=sum(map(lambda x:2**(int(x)-1),input().split()))
  k.append((a,c))

dp=[2**100 for i in range(2**n)]
dp[0]=0
for i in k:
  for j in range(2**n):
    dp[i[1]|j]=min(dp[i[1]|j],dp[j]+i[0])
if dp[-1]==2**100:
  print(-1)
else:
  print(dp[-1])

Submission status: Accepted

Solution code:
def f(L):
    X=0
    for k in L:
        X+=2**(k-1)
    return X

N,M=map(int,input().split())
H=2**N
inf=float("inf")

DP=[inf for _ in range(H)]
DP[0]=0

for _ in range(M):
    A,B=map(int,input().split())
    C=f(list(map(int,input().split())))

    for k in range(H):
        DP[k|C]=min(DP[k|C],DP[k]+A)

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ans=[float("inf")]*(2**n)
ans[0]=0
for i in range(m):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    tmp=0
    for j in c:
        tmp+=2**(j-1)
    na=ans.copy()
    for j in range(2**n):
        if ans[j|tmp]>na[j]+a:
            ans[j|tmp]=na[j]+a
if ans[2**n-1]==float("inf"):
    print(-1)
else:
    print(ans[2**n-1])

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    import itertools
    
    mod=10**9+7
    N,M=MI()
    a=[0]*M
    b=[0]*M
    c=[]
    
    for i in range(M):
        a[i],b[i]=MI()
        cc=LI()
        for j in range(b[i]):
            cc[j]-=1
        c.append(cc)
        
    N2=pow(2,N)
    inf=10**10
    
    def encode(L):
        temp=0
        for i in range(len(L)):
            temp+=L[i]<<i
        return temp
            
    
    dp=[[inf]*N2 for _ in range(M+1)]
    # i番目の鍵までで状態jを達成できる最小値
    
    dp[0][0]=0
    for i in range(M):
        for ite in itertools.product([0,1], repeat=N):
            L=list(ite)
            j=encode(L)
            for k in c[i]:
                L[k]=1
            nj=encode(L)
            # print(i,ite,j,nj)
            if dp[i][j]!=inf:
                dp[i+1][j]=min(dp[i+1][j], dp[i][j])
                dp[i+1][nj]=min(dp[i+1][nj], dp[i][j]+a[i])
        
    ans=dp[-1][-1]
    if ans==inf:
        ans=-1
    print(ans)
    
    # for i in range(M+1):
    #     print(dp[i])
                
    

main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
dp =[float("INF")]*(2**N)
dp[0] = 0
for i in range(1,M+1):
    a,b = map(int,input().split())
    tmp = 0
    for c in list(map(int,input().split())):
        tmp += 1 << (c-1)
    for j in range(2**N):
        target = j|tmp
        dp[target] = min(dp[j]+a,dp[target])
if dp[-1] == float("INF"):
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

def unset_nth_bit(S, j):
    # Sの右からj bit目を0にする
    return S & ~(1 << j)

def set_nth_bit(S, j):
    # Sの右からj bit目を1にする
    return S | (1 << j)

def bit(S, j):
    # Sの右からj bit目(0-indexed)
    return (S>>j)&1

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

a = []
c = []
for i in range(M):
    p, q = map(int, input().split())
    a.append(p)
    c.append(list(map(int, input().split())))

dp = [[INF for j in range(1<<N)] for i in range(M+1)]
dp[0][0] = 0

for i in range(M):
    for S in range(1<<N):
        SS = S
        for cc in c[i]:
            SS = set_nth_bit(SS, cc-1)
        dp[i+1][SS] = min(dp[i+1][SS], dp[i][S] + a[i])
        dp[i+1][S] = min(dp[i+1][S], dp[i][S])

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
key=[]
for _ in range(m):
  a,b=map(int,input().split())
  c=list(map(int,input().split()))
  bi=0
  for i in c:
    bi+=2**(i-1)
  key.append([a,bi])
dp=[10**10]*(2**n)
dp[0]=0
for k in key:
  for b in range(2**n):
    dp[b|k[1]]=min(dp[b|k[1]],dp[b]+k[0])
if dp[-1]==10**10:
  print(-1)
else:
  print(dp[-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
keys=[None]*m
INF = 10**10
dp=[INF]*(2**n)
dp[0]=0
for i in range(m):
  a,b=map(int,input().split())
  c=list(map(int,input().split()))
  cond=0
  for j in c:
    cond+=2**(j-1)
  keys[i]=[a,cond]
for key in keys:
  for sta in range(2**n):
        dp[sta|key[1]]=min(dp[sta|key[1]],dp[sta]+key[0])
print(dp[-1] if dp[-1] != INF else -1)

Submission status: Accepted

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

N, M = map(int, input().split())
ks = []

for _ in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    T = 0
    
    for ci in c:
        T += 1<<(ci-1)
    
    ks.append((a, T))

dp = [10**18]*(1<<N)
dp[0] = 0

for S in range(1<<N):
    for a, T in ks:
        dp[S|T] = min(dp[S|T], dp[S]+a)

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dp = [float("inf") for i in range(1 << n)]
dp[0] = 0
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    bit = 0
    for j in range(b):
        bit |= 1 << (c[j] - 1)
    for j in range(1 << n):
        dp[j | bit] = min(dp[j | bit], dp[j] + a)
if dp[-1] == float("inf"):
    print("-1")
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[None]*m
b=[None]*m
c=[None]*m
for i in range(m):
  a[i],b[i]=map(int,input().split())
  c[i]=list(map(int,input().split()))
INF=10**18
dp=[INF for _ in  range(1<<n)]
dp[(1<<n)-1]=0
for bit in range((1<<n)-2,-1,-1):
  for u in range(m):
    dumy=bit
    flag=0
    for i in c[u]:
      i-=1
      if not ((bit>>i) & 1):
        dumy|=(1<<i)
        flag=1
    if flag:
      dp[bit]=min(dp[bit],dp[dumy]+a[u])
print([dp[0],-1][dp[0]==INF])

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

INF = 10**6

n, m = map(int, input().split())
dp = [INF] * (2**n)
dp[0] = 0
for i in range(m):
    a, b = map(int, input().split())
    bit = ['0'] * n
    for x in set(map(int, input().split())):
        bit[x-1] = '1'
    bit = int(''.join(bit), 2)
    for j in range(2**n-1, -1, -1):
        dp[j|bit] = min(dp[j|bit], a + dp[j])
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

INF = 10**6

n, m = map(int, input().split())
dp = [INF] * (2**n)
dp[0] = 0
for i in range(m):
    a, b = map(int, input().split())
    bit = ['0'] * n
    for x in set(map(int, input().split())):
        bit[x-1] = '1'
    bit = int(''.join(bit[::-1]), 2)
    for j in range(2**n-1, -1, -1):
        dp[j|bit] = min(dp[j|bit], a + dp[j])
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
"""
bitDP
dp[j] => jの二進数表記で1になっている桁数と同じ番号の宝箱を全て開けるのに必要な費用の最小値
"""

N,M = map(int,input().split())
dp = [float("INF")]*(2**N)
dp[0] = 0
for _ in range(M):
    a,b = map(int,input().split())
    C = list(map(int,input().split()))
    key = 0
    for c in C:
        key += 1 << (c-1)
    for j in range(2**N-1,-1,-1):
        dp[j|key] = min(dp[j|key],dp[j]+a)

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
dp=[10**20]*(1<<n)
dp[0]=0
for i in range(m):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    bit=0
    for j in c:bit|=1<<(j-1)
    for j in range(1<<n):
        dp[j|bit]=min(dp[j|bit],dp[j]+a)
if dp[-1]==10**20:print(-1)
else:print(dp[-1])

Submission status: Accepted

Solution code:
from collections import defaultdict
INF = 10**13
N, M = map(int, input().split())
A = []
C = []
for m in range(M):
    a, b = map(int, input().split())
    A += [a]
    c = list(map(int, input().split()))
    C += [sum(map(lambda x: 2**(x-1), c))]
dp = [INF for i in range(2**N)]
dp[0] = 0
for i in range(2**N):
    for j in range(M):
        dp[i | C[j]] = min(dp[i] + A[j], dp[i | C[j]])

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())
INF = 10 ** 10
dp = [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 j in range(len(c)):
    key += (1 << (c[j] - 1))
  for j in range(len(dp) - 1, -1, -1):
    if dp[j] == INF:
      continue
    dp[j | key] = min(dp[j | key], dp[j] + a)

print((dp[-1], -1)[dp[-1] == INF])

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect

n,m=map(int,input().split())
k=2**n
inf=10**7
d=[[inf]*k for _ in range(m+1)]
for i in range(m+1):
  d[i][0]=0
for i in range(m):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    res=0
    for x in c:
        res+=2**(x-1)
    for j in range(2**n):
        jx=j|res
        d[i+1][j]=min(d[i+1][j],d[i][j])
        d[i+1][jx]=min(d[i][jx],d[i][j]+a,d[i+1][jx])
if d[-1][-1]==10**7:
  print(-1)
else:
  print(d[-1][-1])

Submission status: Accepted

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

n, m = map(int, input().split())
ac = []
for i in range(m):
    a, b = map(int, input().split())
    tmpc = map(int, input().split())
    c = sum(1 << (ci - 1) for ci in tmpc)
    ac.append((a, c))

# 解説AC
dp = [[0] + [pow(10, 9)] * (pow(2, n) - 1)]
for i, (ai, ci) in enumerate(ac, 1):
    dp.append(dp[-1][:])
    for j in range(pow(2, n)):
        tmp = min(dp[i - 1][j | ci], dp[i - 1][j] + ai)
        dp[i][j | ci] = min(tmp, dp[i][j | ci])
print(-1 if dp[-1][-1] == pow(10, 9) else dp[-1][-1])

Submission status: Accepted

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

n, m = map(int, input().split())
abc = []
for i in range(m):
    a, b = map(int, input().split())
    tmpc = map(int, input().split())
    c = sum(1 << (ci - 1) for ci in tmpc)
    abc.append([a,b,c])

# 解説AC
dp = [[0] + [pow(10, 9)] * (pow(2, n) - 1)]
for i, (ai, _, ci) in enumerate(abc, 1):
    dp.append(dp[-1][:])
    for j in range(pow(2, n)):
        tmp = min(dp[i - 1][j | ci], dp[i - 1][j] + ai)
        dp[i][j | ci] = min(tmp, dp[i][j | ci])
print(-1 if dp[-1][-1] == pow(10, 9) else dp[-1][-1])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    A, C = [], []
    for _ in range(m):
        a, b = map(int, input().split())
        A.append(a)
        key = 0
        for c in map(int, input().split()):
            key |= 1 << (c - 1)
        C.append(key)

    dp = [f_inf] * (1 << n)
    dp[0] = 0
    for S in range(1 << n):
        for i in range(m):
            key, cost = C[i], A[i]
            dp[S | key] = min(dp[S | key], dp[S] + cost)
    print(dp[-1] if dp[-1] != f_inf else -1)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    A = [0] * M
    C = [0] * M
    for i in range(M):
        A[i], _ = map(int, input().split())
        C[i] = sum(2 ** (int(c) - 1) for c in input().split())

    INF = 10 ** 18
    dp = [INF] * (2 ** N)
    dp[0] = 0
    for a, c in zip(A, C):
        for s in range(2 ** N):
            dp[s | c] = min(dp[s | c], dp[s] + a)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
bs = [None]*m
a = [None]*m
for i in range(m):
    a[i],_ = map(int, input().split())
    c = list(map(int, input().split()))
    b = 0
    for num in c:
        b += 1<<(num-1)
    bs[i] = b
dp = [[float("inf")]*(1<<n) for _ in range(m+1)]
for i in range(m+1):
    dp[i][0] = 0
for i in range(m):
    for j in range(1<<n):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        b = j | bs[i]
        dp[i+1][b] = min(dp[i+1][b], dp[i][j]+a[i])
ans = dp[m][(1<<n)-1]
if ans==float("inf"):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n, m = map(int, input().split())
    price = [0]*m
    typesnum = [0]*m
    keybit=[0]*m
    for i in range(m):
        price[i], typesnum[i] = map(int, input().split())
        keybit[i] = sum(map(lambda x: 2**(int(x)-1), input().split()))
    dp = [10**9]*(1 << n)
    dp[0]=0
    for bit in range(1 << n):
        for i in range(m):
            dp[bit | keybit[i]] = min(dp[bit | keybit[i]], dp[bit]+price[i])
    if dp[-1] == 10**9:
        dp[-1] = -1
    print(dp[-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
inf = 10 ** 10
dp = [inf for _ in range(2 ** n)]
dp[0] = 0
bin_s = [2 ** i for i in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    clst = list(map(int, input().split()))
    tmp = 2 ** n - 1
    for c in clst:
        tmp -= bin_s[c - 1]
    for i in range(2 ** n):
        dp[i] = min(dp[i], dp[i & tmp] + a)

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

Submission status: Accepted

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 i in range(b):
    C[i] -=1 #oindex
    s = s|1<<C[i] #それぞれの宝箱の番号で左シフトしてorをとることでどの宝箱を開けられるかを保存。
  key.append((s,a)) #開けられる宝箱とコストを保存
#print(key)
INF = float("inf")  
dp = [INF for _ in range(1<<N)]
dp[0] = 0
#配るDP O(2^N*M)
for s in range(1<<N): #小さい順からやるとうまく遷移ができる。
  for i in range(M): #すべてのカギについて遷移を試す。
    t = s|key[i][0] #現在の宝箱の状態sに対して、新しい鍵を加えたときに開けられる宝箱の状態。 
    dp[t] = min(dp[t],dp[s] + key[i][1])
#print(dp)
if dp[-1] == INF:
  ans = -1
else:
  ans = dp[-1]
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
# abl = []
# cl = []

dp = [ [10**9]*(2**n) for _ in range(m+1) ]
dp[0][0] = 0
for i in range(m):
    a,b = map(int, input().split())
    cl = list(map(int, input().split()))
    cbit = 0
    for c in cl:
        cbit += 2**(c-1)
    
    for j in range(2**n):
        if dp[i][j] == 10**9:
            continue
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
        dp[i+1][j|cbit] = min(dp[i][j]+a, dp[i][j|cbit], dp[i+1][j|cbit])

ans = dp[m][2**n-1]
if ans >= 10**9:
    ans = -1

print(ans)

Submission status: Accepted

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

INF = float("inf")
dp = [INF for i in range(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 c in C:
        key += 2**(c-1)
    for j in range(len(dp)-1, -1, -1):
        if dp[j] == INF:
            continue
        if dp[j | key] > dp[j] + a:
            dp[j | key] = dp[j] + a
            
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
keys = dict()
min_cost = dict()
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    bit = 0
    for x in c:
        bit |= 1 << (x - 1)
    if bit in keys and keys[bit] <= a:
        continue
    keys[bit] = a
    min_cost[bit] = a

for i in range(1, 1 << n):
    if not i in min_cost:
        continue 
    for bit, cost in keys.items():
        bit |= i
        if i != bit:
            if bit in min_cost:
                min_cost[bit] = min(min_cost[bit], min_cost[i] + cost)
            else:
                min_cost[bit] = min_cost[i] + cost

if not (1 << n) - 1 in min_cost:
    print(-1)
else:
    print(min_cost[(1 << n) - 1])