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

Solution (Python):
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()

Solution (Python):


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

Solution (Python):


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)

Solution (Python):
n, m = map(int, input().split())
dp = [10**9] * (2**n)
dp[0] = 0
for i in range(m):
    a, _ = map(int, input().split())
    
    c = list(map(int, input().split()))
    t = 0
    
    
    
    for x in c:
        t |= 1 << (x-1)
    for b in range(2**n):
        
        
        dp[b|t] = min(dp[b|t], dp[b]+a)
if dp[-1] > 10**8:
    print(-1)
else:
    print(dp[-1])

Solution (Python):
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])
    

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

Solution (Python):
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])

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):



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):
        
        e = c | d
        
        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])

Solution (Python):


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

Solution (Python):
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])

Solution (Python):

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)




dp = [10**9 for j in range(2**n)]
dp[0] = 0









for i in range(m):
    for j in range(2**n):
        
        dp[j|c[i]] = min(dp[j|c[i]],dp[j] + a[i])

        
        
    


if dp[2**n-1]<10**9-1:
    print(dp[2**n-1])
else:
    print(-1)

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):

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

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    p, INF = 1 << N, 1 << 60
    
    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()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    p, INF = 1 << N, 1 << 60
    
    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()

Solution (Python):

def main():
    N, M = map(int, input().split())
    p, INF = 1 << N, 1 << 60
    
    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()

Solution (Python):
import sys
input = sys.stdin.readline

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


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

Solution (Python):
import sys
input = sys.stdin.readline

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


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

Solution (Python):
import sys
input = sys.stdin.readline

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


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
        


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

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

dp = [float("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
        


if dp[(1<<n) - 1] == float("inf"):
    ans = -1
else:
    ans = dp[(1<<n) - 1]

print(ans)

Solution (Python):
N, M = map(int, input().split())
ab = []
d = [0 for _ in range(M)]
for i in range(M):
  ab.append(list(map(int, input().split())))
  for k in list(map(int, input().split())):
    d[i] += 2**(k-1)
  
infty = 10**8
  
dp = [infty for j in range(2**N)]

dp[0] = 0

for i in range(M):
  for j in range(2**N):
    if dp[j|d[i]] > dp[j] + ab[i][0]:
      dp[j | d[i]] =  dp[j] + ab[i][0]

ans = dp[2**N-1] if dp[2**N-1] != infty else -1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

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

    dp[0] = 0
    for s in range(1 << N):
        for i in range(M):
            t = s | keys[i][0]
            cost = dp[s] + keys[i][1]
            dp[t] = min(dp[t],cost)
    
    if dp[-1] == float('inf'):
        print(-1)
    else:
        print(dp[-1])
            
main()

Solution (Python):
N,M=map(int,input().split())
L=2**N
l=[float("inf")]*L
l[0]=0
r=(1,2,4,8,16,32,64,128,256,512,1024,2048)
for i in range(M):
    s=0
    a,b=map(int,input().split())
    c=tuple(map(int,input().split()))
    for j in c:
        s+=r[j-1]
    for j in range(L):
        l[j|s]=min(l[j|s],l[j]+a)
if l[-1]==float("inf"):
    print(-1)
else:
    print(l[-1])

Solution (Python):
n,m = map(int,input().split())
dp = [10**9]*(2**n)
dp[0] = 0
for _ in range(m):
  a,_ = map(int,input().split())
  c = list(map(int,input().split()))
  t = 0
  for x in c:
    t |= 1<<(x-1)
  for b in range(2**n):
    if dp[b|t] > dp[b]+a:
      dp[b|t] = dp[b] + a
if dp[-1] > 10**8:
  print(-1)
else:
  print(dp[-1])

Solution (Python):
n,m = map(int,input().split())
dp = [10**9]*(2**n)
dp[0] = 0
for _ in range(m):
  a,_ = map(int,input().split())
  c = list(map(int,input().split()))
  t = 0
  for x in c:
    t |= 1<<(x-1)
  for b in range(2**n):
    dp[b|t] = min(dp[b|t],dp[b]+a)
if dp[-1] > 10**8:
  print(-1)
else:
  print(dp[-1])

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    p = 1 << N
    INF = 1 << 60
    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):
            if dp[x | y] > dp[y] + a:
                dp[x | y] = dp[y] + a
    ans = dp[-1] if dp[-1] != INF else -1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N,M = map(int, input().split())
L = []
C = []
for i in range(M):
    L.append([int(l) for l in input().split()])
    C.append([int(c) for c in input().split()])
    
dp = [10**8+1 for j in range(2**N)]
dp[0] = 0

for i in range(1, M+1):
    temp = 0
    for k in range(len(C[i-1])):
        temp += 2**(C[i-1][k]-1)
    for j in range(2**N):
        if i == 1:
            if j | temp == temp and j != 0:
                dp[j] = L[i-1][0]

        else:
            dp[temp | j] = min(dp[temp | j], dp[j]+L[i-1][0])
      
if dp[-1] >= 10**8+1:
    print(-1)
else:
    print(dp[-1])

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    N,M = map(int,input().split())
    full = 2**N
    dp = [float("inf")]*full
    dp[0] = 0


    for m in range(M):
        a,b = map(int, input().split())
        C = list(map(int, input().split()))
        
        state = 0
        for c in C:
            state += 2**(c-1)

        
        
        for i in range(full):
            if dp[i] != float("inf"):
                dp[i|state] = min(dp[i]+a,dp[i|state])

    if dp[-1]==float("inf"):
    
        return -1

    return dp[-1]

print(main())

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    p = 1 << N
    dp = [10 ** 10] * 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):
            if dp[x | y] > dp[y] + a:
                dp[x | y] = dp[y] + a
    ans = dp[-1] if dp[-1] != 10 ** 10 else -1
    print(ans)


if __name__ == "__main__":
    main()

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

INF = 10**7
p = 1<<n
dp = [INF]*p
dp[0] = 0

for _ in range(m):
    a, _ = map(int, input().split())
    c = sum([1<<(int(i)-1) for i in input().split()])
    def k(s):
        dp[s|c] = dp[s] + a
    [k(s) for s in range(p) if dp[s|c] > dp[s] + a]
ans = dp[-1]
if ans==INF:
    ans = -1
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    p = 1 << N
    INF = 10 ** 10
    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):
            if dp[x | y] > dp[y] + a:
                dp[x | y] = dp[y] + a
    ans = dp[-1] if dp[-1] != INF else -1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    p = 2 ** N
    dp = [float("inf")] * p
    dp[0] = 0
    for _ in range(M):
        a, _ = map(int, input().split())
        x = sum(2 ** (i - 1) for i in map(int, input().split()))
        for y in range(p):
            if dp[x | y] > dp[y] + a:
                dp[x | y] = dp[y] + a
    ans = dp[-1] if dp[-1] != float("inf") else -1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    p = 1 << N
    dp = [float("inf")] * p
    dp[0] = 0
    for _ in range(M):
        a, _ = map(int, input().split())
        x = sum(1 << (int(i) - 1) for i in input().split())
        for y in range(p):
            if dp[x | y] > dp[y] + a:
                dp[x | y] = dp[y] + a
    ans = dp[-1] if dp[-1] != float("inf") else -1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    p = 1 << N
    dp = [float("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):
            if dp[x | y] > dp[y] + a:
                dp[x | y] = dp[y] + a
    ans = dp[-1] if dp[-1] != float("inf") else -1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

def main():
    N, M = map(int, input().split())
    p = 1 << N
    dp = [float("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):
            if dp[x | y] > dp[y] + a:
                dp[x | y] = dp[y] + a
    ans = dp[-1] if dp[-1] != float("inf") else -1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    p = 1 << N
    dp = [float("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):
            if dp[x | y] > dp[y] + a:
                dp[x | y] = dp[y] + a
    ans = dp[-1] if dp[-1] != float("inf") else -1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

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

a = [0] * M
b = [0] * M
c = [[] for _ in range(M)]
for i in range(M):
    a[i], b[i] = map(int, input().split())
    c[i] = list(map(int, input().split()))

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

movement = []
for i in range(M):
    move = 0
    for j in range(len(c[i])):
        move += 2 ** (c[i][j]-1)
    movement.append(move)

for i in range(2**N):
    for j in range(M):
        move2 = movement[j] 
        if cost[i|move2] > cost[i]+a[j]:
            cost[i|move2] = cost[i]+a[j]

if cost[2**N-1] == inf:
    print(-1)
else:
    print(cost[2**N-1])

Solution (Python):
n,m = map(int,input().split())
inf = float('inf')
dp = [inf]*(2**n)
dp[0] = 0
for i in range(m):
  a,b = map(int,input().split())
  c = sum([ 1<< (p-1) for p in list(map(int,input().split()))])
  for j in range(2**n):
    dp[j|c] =min(dp[j|c] ,dp[j]+a)
    
print(dp[2**n-1] if dp[2**n-1] != inf else -1)

Solution (Python):



import sys
input = sys.stdin.readline
N, M = map(int, input().split())
dp = [float("inf")] * (1<<N)
for _ in range(M):
    a, _ = map(int, input().split())
    C = list(map(int, input().split()))
    s = 0
    for c in C:
        s |= 1 << c-1
    dp[s] = min(dp[s], a)
for i in range(1<<N):
    for j in range(1<<N):
        dp[i|j] = min(dp[i|j], dp[i]+dp[j])
ans = dp[-1]
print(ans if ans!=float("inf") else -1)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



N,M = II()
a = [0]*M
b = [0]*M
c = []
x = []
for i in range(M):
    a[i],b[i] = II()
    new_c = III()
    c.append(new_c)
    k = 0
    for c1 in new_c:
        k += 2**(c1-1)
    x.append(k)

dp = [-1]*(2**N)
dp[0] = 0
for i in range(M):
    if dp[x[i]]==-1:
        dp[x[i]] = a[i]
    else:
        dp[x[i]] = min(dp[x[i]], a[i])
    for j in range(2**N-1):
        if dp[j]==-1:
            continue
        else:
            if dp[j|x[i]]==-1:
                dp[j|x[i]] = dp[j] + dp[x[i]]
            else:        
                dp[j|x[i]] = min(dp[j|x[i]], dp[j] + dp[x[i]])

print(dp[2**N-1])

Solution (Python):
N,M = map(int,input().split())
K = [[0, 0] for i in range(M)]
for i in range(M) :
    a,b = map(int,input().split())
    cx = tuple(map(int,input().split()))
    s = 0
    for c in cx :
        s = s | (1 << (c-1))
    K[i] = [s, a]

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

for bit in range(1 << N) :
    for i in range(M) :
        s,a = K[i]
        t = bit | s
        cost = dp[bit] + a
        dp[t] = min(dp[t], cost)

ans = dp[-1] if dp[-1] != INF else -1

print(ans)

Solution (Python):
N, M = map(int, input().split())
INF = float("inf")
V = [INF] * (1<<N)
V[0] = 0
for i in range(M):
  v,_ = map(int, input().split())
  b = 0
  s = list(map(int, input().split()))
  for a in s:
    b |= (1<<(a-1))
  V[b] = min(V[b], v) 

vbs = [] 
for b,v in enumerate(V):
  if v == INF:
    continue
  vbs.append((v,b))

for v,b in vbs:
  for c in range(1<<N):
    if V[c] == INF:
      continue
    V[b|c] = min(V[b|c], V[b]+V[c])

print(V[-1] if V[-1] < INF else -1)

Solution (Python):


import sys

sys.setrecursionlimit(100000)
MOD = 10 ** 9 + 7
INF = float('INF')




N, M = [int(x) for x in input().split()]
COSTS = [INF] * (1 << N)
COSTS[0] = 0
KEYS = [0]
A = [0]
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    key = 0
    for c in C:
        key |= (1 << (c-1))
    A.append(a)
    KEYS.append(key)

for pat in range(1 << N):
    for a, key in zip(A, KEYS):
        COSTS[pat | key] = min(COSTS[pat | key], COSTS[pat] + a)

ans = COSTS[(1 << N) - 1] 
if ans == INF:
    ans = -1 
print(ans)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
cost = []
key = []
for _ in range(m):
    a,b = LI()
    cost.append(a)
    c = LI()
    tmp = 0
    for i in c:
        tmp |= 1 << (i-1)
    key.append(tmp)
dp = [[inf]*(m+1) for _ in range(2**n)]
dp[0][0] = 0
for i in range(2**n):
    M = min(dp[i])
    for j in range(1,m+1):
        s = key[j-1]
        if i|s > i:
            dp[i|s][j] = min(dp[i|s][j],M + cost[j-1])
if min(dp[-1]) == inf:
    print(-1)
else:
    print(min(dp[-1]))

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
cost = []
key = []
for _ in range(m):
    a,b = LI()
    cost.append(a)
    c = LI()
    tmp = 0
    for i in c:
        tmp |= 1 << (i-1)
    key.append(tmp)
dp = [[inf]*(m+1) for _ in range(2**n)]
dp[0][0] = 0
for i in range(2**n):
    for j in range(m):
        dp[i][j+1] = min(dp[i][j+1],dp[i][j])
    for j in range(1,m+1):
        s = key[j-1]
        if i|s > i:
            dp[i|s][j] = min(dp[i|s][j],dp[i][j-1] + cost[j-1])
if min(dp[-1]) == inf:
    print(-1)
else:
    print(min(dp[-1]))

Solution (Python):
I=lambda:map(int,input().split());n,m=I();d=[0]+[9**9]*2**n
while m:
 m-=1;a,_=I();s=sum(1<<c-1for c in I())
 for j in range(2**n):d[s|j]=min(d[s|j],d[j]+a)
print(d[-2]%9**9or-1)

Solution (Python):
n,m=map(int,input().split())
a=[]
k=[]
for _ in range(m):
  a.append(list(map(int,input().split()))[0])
  k.append(sum(2**(int(i)-1)for i in input().split()))
inf=float('inf')
dp=2**n*[inf]
dp[0]=0
for i in range(2**n):
  for j in range(m):
    dp[i|k[j]]=min(dp[i|k[j]],dp[i]+a[j])
print(dp[-1]if inf!=dp[-1]else-1)

Solution (Python):
N,M=map(int,input().split())
inf=12*(10**5)+1

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

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

    for j in range(2**N):
        dp[j|c]=min(dp[j|c],dp[j]+a)


print(dp[2**N-1] if dp[2**N-1]!=inf else -1)

Solution (Python):
I=lambda:map(int,input().split())
n,m=I()
d=[0]+[9**9]*2**n
while m:
 m-=1;a,_=I();s=sum(1<<c-1for c in I())
 for j in range(2**n):d[s|j]=min(d[s|j],d[j]+a)
print(d[-2]%9**9or-1)

Solution (Python):
import numpy as np
(n,m),*d = [list(map(int, s.split())) for s in open(0)]

inf = 100000000
dp = np.full([2]*n, inf, dtype=np.int)
dp[tuple([0]*n)] = 0

for i in range(m):
    a = d[2*i][0]
    b = d[2*i][1]
    c = d[2*i+1]
    
    l0 = [slice(None)]*n
    for x in c:
        l0[x-1] = slice(None,1)
    dp = np.minimum(dp, dp[tuple(l0)]+a)
    
ans = dp[tuple([1]*n)]
if ans == inf:
    print(-1)
else:
    print(ans)

Solution (Python):
n, m = map(int, input().split())
ac = []
for _ in range(m):
    a,_ = map(int, input().split())
    c = sum([2**(int(i)-1) for i in input().split()])
    ac.append([a, c])
dp = [float('inf')] * 2**n
dp[0] = 0
for s in range(2**n):
    for a, c in ac:
        t = s|c
        cost = dp[s] + a
        dp[t] = min(dp[t], cost)
ans = dp[-1]
if ans == float('inf'):
    ans = -1
print(ans)

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = 2**n
    inf = 10**7
    dp = [inf]*p
    dp[0] = 0
    for _ in range(m):
        a, _ = map(int, input().split())
        c = sum([1<<(int(i)-1) for i in input().split()])
        for s in range(p):
                if dp[s|c] > dp[s] + a:
                    dp[s|c] = dp[s] + a
    ans = dp[-1]
    if ans == inf:
        ans = -1
    print(ans)

if __name__ == '__main__':
    main()