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

AB = []
AB_append = AB.append
C = []
C_append = C.append
for _ in range(M):
    a, b = map(int, input().split())
    AB_append((a, b))
    c = list(map(int, input().split()))
    C_append(c)


ans = [10 ** 18] * (2 ** (N + 1))
ans[0] = 0
for i in range(M):
    tmp = 0
    for j in C[i]:
        tmp += 2 ** (j - 1)
    # print ('tmp', tmp)
    for j in range(2 ** N):
        # print (j, '-->', j | tmp)
        if ans[j] == 10 ** 18:
            pass
        else:
            ans[j | tmp] = min(ans[j | tmp], ans[j] + AB[i][0])

if ans[2 ** N - 1] == 10 ** 18:
    print (-1)
    exit()
print (ans[2 ** N - 1])

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    INF = int(1E8)
    dp = [INF for _ in range(2**N)]
    A = [None for _ in range(M)]
    for j in range(M):
        a, b = map(int, input().split())
        C = list(map(int, input().split()))
        ind = 0
        for c in C:
            ind += 2**(c-1)
        A[j] = (ind, a)
        dp[ind] = min(dp[ind], a)

    Id = [i for i in range(2**N)]
    Id.sort(key=lambda x: bin(x).count('1'))

    for x in Id:
        for ind, a in A:
            dp[x|ind] = min(dp[x|ind], dp[x]+a)
    if dp[2**N-1] >= INF:
        print(-1)
    else:
        print(dp[2**N-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
N,M = map(int,input().split(' '))

a = []
b = []
c = []
for i in range(1,M+1):
	a_,b_ = map(int,input().split(' '))
	a.append(a_)
	#b.append(b_)
	c_ = list(map(int,input().split(' ')))
	op = 0
	for t in c_:
		op += (1 << (t-1))
	c.append(op)

dic = defaultdict(lambda: sum(a)+1)
dic[0] = 0
for i in range(M):
	val = a[i]
	op = c[i]
	keys = list(dic.keys())
	for k in keys:
		dic[k | op] = min(dic[k|op] , dic[k] + val)

if dic[2**N-1] == sum(a)+1:
	print(-1)
else:
	print(dic[2**N-1])

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
from itertools import combinations
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

def subsets(items):
    _subsets_=[]
    for i in range(len(items) + 1):
        for c in combinations(items, i):
            _subsets_.append(c)
    return _subsets_

INF = 999999999999999999999999

n,m = get_nums_l()

# ある扉の組み合わせを鍵1本で開けられる最小コストのリスト
keys = [INF] * (2 ** (n+2))

for _ in range(m):
    cost, b = get_nums_l()
    ccc = get_nums_l()

    # print(cost,b)


    for s in subsets(ccc):
        keyn = 0
        # print(s)
        for c in s:
            keyn += 2 ** c
        
        #print("keyn", keyn)
        if keys[keyn] > cost:
            keys[keyn] = cost

# print(keys)

# そもそも開けられない扉があったら無理
for i in range(1,n+1):
    if keys[2**i] == INF:
        print(-1)
        exit()

memo=[None] * (2 ** (n+2))

def solve(targets):

    lent = len(targets)
    
    # print(targets)

    if lent == 0:
        return 0

    if lent == 1:
        memo[2*list(targets)[0]] = keys[2*list(targets)[0]]
        # print(targets, keys[2**list(targets)[0]])
        return keys[2**list(targets)[0]]

    # all_s = set(targets)

    keyn=0
    for c in targets:
        keyn += 2 ** c
    
    if memo[keyn]:
        return memo[keyn]

    _min = keys[keyn]

    for s in subsets(targets):
        if len(s) in (0, lent):
            continue
        rev = targets.difference(s)
        cost = solve(s) + solve(rev)
        if _min > cost:
            _min = cost
    memo[keyn] = _min
    # print(targets, memo[keyn])
    return _min


ans = solve(set(range(1, n+1)))
# print(memo)
print(ans if ans < INF else -1)

Submission status: Accepted

Solution code:
import sys
import heapq

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    cost = dict()
    for i in range(2 ** N): cost[i] = -1
    cost[0] = 0
    for i in range(M):
        a, b = map(int, input().split())
        c = [int(c) for c in input().split()]
        bit = 0
        for j in c: bit += 2 ** (j - 1)
        for i in range(2 ** N):
            if cost[i] > -1:
                if cost[i | bit] > -1:
                    cost[i | bit] = min(cost[i | bit], cost[i] + a)
                else: cost[i | bit] = cost[i] + a

    #print(cost)

    print(cost[2 ** N - 1])
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict

N, M = map(int, input().split())
a = []
c = []
dp = defaultdict(lambda: 1000000000)
for i in range(M):
    ai, bi = map(int, input().split())
    a.append(ai)
    c.append(sum([1 << int(ci) - 1 for ci in input().split()]))

dp[0] = 0
for i in range(M):
    for k, v in list(dp.items()):
        dp[k | c[i]] = min(dp[k | c[i]], dp[k] + a[i])
print(dp[(1 << N) - 1] if (1 << N) - 1 in dp else -1)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
from copy import deepcopy, copy

import queue
from collections import deque



def main():
    box_num, kagi_num = map(int, input().split())

    kagi_data = defaultdict(lambda: 10 ** 10)
    for i in range(kagi_num):
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        money = a[0]
        ind = 0
        for ele in b:
            ind += 2 ** (ele - 1)
        kagi_data[ind] = min(kagi_data[ind], money)

        for key, value in list(kagi_data.items()):
            kari = ind | key
            kagi_data[kari] = min(money + value, kagi_data[kari])

    ans = kagi_data[2 ** (box_num) - 1]
    if ans == 10 ** 10:
        print(-1)
    else:
        print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF = 10**10

N, M = map(int, input().split())
costs = []
keys = []
for _ in range(M):
    A, B = map(int, input().split())
    cs = list(map(int, input().split()))
    costs.append(A)
    # 鍵を2進数化する
    key = 0
    for c in cs:
        key |= 1<<(c-1)
    keys.append(key)

# [1]の個数で分類する
maskss = [[] for _ in range(N+1)]
num1s = [0] * (2**N)
for S in range(2**N):
    num = bin(S).count('1')
    maskss[num].append(S)
    num1s[S] = num

dpAll = [INF] * (2**N)
for S in range(2**N):
    for cost, key in zip(costs, keys):
        if S & key == S:
            if cost < dpAll[S]:
                dpAll[S] = cost

dp = [INF] * (2**N)
for S in range(2**N):
    cost = dpAll[S]
    num1 = num1s[S]
    for k in range(1, (num1+1)//2+1):
        for mask in maskss[k]:
            if mask & S == mask:
                m2 = S^mask
                c2 = dp[mask] + dp[m2]
                if c2 < cost:
                    cost = c2
    dp[S] = cost

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

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
from copy import deepcopy, copy

import queue
from collections import deque



def divisor(n): #nの約数を全て求める
    i = 1
    table = set()
    while i * i <= n:
        if n%i == 0:
            table.add(i)
            table.add(n//i)
        i += 1
    return table

ans = 10 ** 10

def check(box_num, kagi_num, kagi_data, ind, now_data_kari, money, data):
    now_data = copy(now_data_kari)

    if ind == box_num:
        for i in range(box_num):
            if now_data[i] == 0:
                break
        else:
            global ans
            ans = min(ans, money)
        return


    if now_data[ind]:
        check(box_num, kagi_num, kagi_data, ind + 1, now_data, money, data)
        return

    check_set = set()
    for i in range(len(kagi_data[ind + 1])):
        aaa = kagi_data[ind + 1][i]
        now_data = copy(now_data_kari)

        bbb = ['0' for i in range(box_num)]
        flg = 1
        for ele in data[aaa][2]:
            if now_data[ele - 1] == 0:
                now_data[ele - 1] = 1
                flg = 0
            if ele >= ind + 1:
                bbb[ele - 1] = '1'
        if flg:
            continue
        bbb = ''.join(bbb)
        if bbb in check_set:
            continue
        check_set.add(bbb)
        check(box_num, kagi_num, kagi_data, ind + 1, now_data, money + data[aaa][0], data)



def main():
    box_num, kagi_num = map(int, input().split())

    data = [0 for i in range(kagi_num)]
    kari = set()

    for i in range(kagi_num):
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        kari |= set(b)
        data[i] = [a[0], a[1], b]


    kagi_data = defaultdict(int)
    for i in range(kagi_num):
        a = data[i]
        aaa = 0
        for ele in a[2]:
            aaa += 2 ** (ele - 1)
        bin_data = bin(aaa)[2:]
        bin_data = bin_data.zfill(box_num)

        if bin_data in kagi_data:
            kagi_data[bin_data] = min(a[0], kagi_data[bin_data])
        else:
            kagi_data[bin_data] = a[0]

        aaaaaa = kagi_data.items()

        for key, value in list(aaaaaa):
            aaa = ['0' for i in range(box_num)]
            for i in range(box_num):
                if key[i] == '1' or bin_data[i] == '1':
                    aaa[i] = '1'
            aaa = ''.join(aaa)
            if aaa in kagi_data:
                kagi_data[aaa] = min(value + a[0], kagi_data[aaa])
            else:
                kagi_data[aaa] = value + a[0]


    # print(kagi_data)
    aaa = ['1' for i in range(box_num)]
    aaa = ''.join(aaa)
    if aaa in kagi_data:
        print(kagi_data[aaa])
    else:
        print(-1)



# def test():
#     for i in :
#         print(i)

if __name__ == '__main__':
    main()
    # test()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    inf = 10 ** 9
    n, m = map(int, input().split())
    dp = [inf] * (1 << n)
    dp[0] = 0

    for _ in range(m):
        a, b = map(int, input().split())
        cc = list(map(int, input().split()))
        mask = 0
        for c in cc:
            mask += 1 << (c - 1)
        for i in range((1 << n) - 1, -1, -1):
            if dp[i] == inf: continue
            ni = i | mask
            if not 0 <= ni < (1 << n): continue
            dp[ni] = min(dp[ni], dp[i] + a)
#        print(dp)
    ans = dp[-1]
    if ans == inf:
        print(-1)
    else:
        print(ans)

main()

Submission status: Accepted

Solution code:
import sys

N,M=map(int, raw_input().split())
dp=[ float("inf") for _ in range(2**N)]
dp[0]=0


for _ in range(M):
	a,b=map(int, raw_input().split())
	C=map(int, sys.stdin.readline().split())

	n=0
	for c in C:
		n+=2**(N-c)

	for k in range(2**N-1):
		dp[n|k]=min(dp[n|k],dp[k]+a)

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
dp = [[int(2e8) for _ in range(2**n)] for _ in range(2)]
dp[0][0] = 0
dp[1][0] = 0
for i in range(m):
    a, _ = map(int, input().split())
    k = sum(map(lambda c: 1 << (c - 1), list(map(int, input().split()))))
    for j in range(2**n):
         dp[(i + 1) % 2][j] = min(dp[(i + 2) % 2][j], dp[i % 2][j])
    for j in range(2**n):
         dp[(i + 1) % 2][j | k] = min(dp[(i + 1) % 2][j | k], dp[i % 2][j] + a)
ans = min(dp[0][-1], dp[1][-1])
if int(1e8) < ans:
    ans = -1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()))
n,m=I()
e=eval('(I()[0],I()),'*m)
dp=[9e9]*2**n
dp[0]=0
for i in range(2**n):
    if dp[i]==9e9:continue
    for a,c in e:
        b=i
        for j in c:b|=2**(n-j)
        dp[b]=min(dp[b],dp[i]+a)
print(-(dp[-1]==9e9)or dp[-1])

Submission status: Accepted

Solution code:
N,M = [int(x) for x in input().split()]
a = []
b = []
c = []
for i in range(M):
  A,B = [int(x) for x in input().split()]
  C = [int(x) for x in input().split()]
  a.append(A)
  b.append(B)
  c.append(C)
c1 = []
for i in range(M):
  l = 0
  for j in c[i]:
  	l = l|1<<(j-1)
  c1.append(l)
cnt = [0]*(1<<N)
dp = [[float('inf')]*(1<<N) for _ in range(M+1)]
dp[0][0] = 0
for i in range(M):
  for j in range(1<<N):
    dp[i+1][j] = min(dp[i][j],dp[i+1][j])
    dp[i+1][j|c1[i]] = min(dp[i][j]+a[i],dp[i+1][j|c1[i]])
if dp[M][-1]!=float("inf"):
  print(dp[M][-1])
else:
  print(-1)
"""
for s in range(1<<N):
    for i in range(N):
        if not s & (1 << i) and s & edges[i] == edges[i]:
            nextS = s| (1 << i)
            disk[nextS] = disk[s] + x[i]
            dp[nextS] = min(dp[nextS], max(dp[s], disk[nextS]))
            disk[nextS] -= cost[i]
print(dp[-1])
"""

Submission status: Accepted

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

ret = [float('inf')] * (1 << N)
for _ in range(M) :
    a, b = map(int, input().split())
    c = 0
    for i in input().split() :
        c |= 1 << (int(i) - 1)
    ret[c] = min(ret[c], a)

for i in range(1 << N) :
    if ret[i] == float('inf') :
        continue
    for j in range(1 << N) :
        k = i | j
        ret[k] = min(ret[k], ret[i] + ret[j])

if ret[-1] == float('inf') :
    print(-1)
else :
    print(ret[-1])

Submission status: Accepted

Solution code:
import sys
from heapq import *

input = sys.stdin.readline

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

error = 10000000000

q = []
minc = [error]*(2**N)
for i in range(M):
	a, b = list(map(int,input().split()))
	c = list(map(int,input().split()))
	c10 = 0
	for ci in c:
		c10 += 2**(ci-1)

	minc[c10] = min(minc[c10],a)

while True:
	tmin = min(minc)
	if tmin==minc[-1]: break
	ti = minc.index(tmin)
	for i, mini in enumerate(minc):
		if mini!=error:
			ni = ti | i
			minc[ni] = min(minc[ni],tmin+mini)
	minc[ti] = error

ans = minc[-1]
if ans==error: ans = -1
print(ans)

Submission status: Accepted

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

dp=[-1]*(2**n)
for i in range(m):
    for j in range(2**n):
        if j|c[i]==c[i]:
            if dp[j]<0:
                dp[j]=a[i]
            else:
                dp[j]=min(dp[j],a[i])
for i in range(m):
    for j in range(2**n):
        if dp[j]<0:
            continue
        if dp[c[i]|j]<0:
            dp[c[i]|j]=dp[j]+a[i]
        else:
            dp[c[i]|j]=min(dp[c[i]|j],dp[j]+a[i])
print(dp[-1])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
box = [float('inf')]*(2**N)

for i in range(M):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    k = 0
    for i in c:
        k += 2**(i-1)
    box[k] = min(box[k],a)
    for j in range(2**N):
        box[(k&j)+(k^j)] = min(box[(k&j)+(k^j)],box[k]+box[j])
if box[-1] == float('inf'):
    print(-1)
else:
    print(box[-1])

Submission status: Accepted

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

dp = [float("inf")]*(2**n)

p = []
used = [True]*(2**n)

for _ in range(m):
    a,b = map(int,input().split())
    c = tuple(map(int,input().split()))
    jkl = 0
    for e in c:
        jkl += 1 << (e-1)
    p.append(jkl)
    dp[jkl] = min(dp[jkl],a)
    used[jkl] = False

tank = []

while True:
    tank = []
    for e in p:
        for ep in p:
            if dp[e|ep] > dp[e]+dp[ep]:
                dp[e|ep] = dp[e]+dp[ep]
                if used[e|ep]:
                    tank.append(e|ep)
                    used[e|ep] = False

    if len(tank) == 0:
        break
    for e in tank:
        p.append(e)

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

Submission status: Accepted

Solution code:
import copy
from collections import defaultdict
N, M = map(int, input().split())
ac = []

dp = defaultdict(lambda: 10 ** 5 + 1)
# dp = {}

for _ in range(M):
    # ab.append(tuple(map(int, input().split())))
    ac.append([int(input().split()[0]), frozenset(map(int, input().split()))])

ac.sort()
for a, cs in ac:
    if dp[cs] > a:
    # if cs not in dp or dp[cs] > a:
        dp[cs] = a
        dp2 = copy.copy(dp)
        for k, v in dp2.items():
            # if not cs <= k:
            k |= cs
            dp[k] = min(v + a, dp[k])


ans = dp[frozenset(range(1, N + 1))]
if ans == 10 ** 5 + 1:
    ans = -1
print(ans)

Submission status: Accepted

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

a = [0] * m
b = [0] * m
c = list()
d = list()

def to_int(c):
    a = [0 , 1, 2, 4, 8, 16 , 32, 64, 128, 256, 512, 1024, 2048]
    result = 0
    for ci in c:
        result += a[ci]
    return result


state = [-1] * 2**n
state[0] = 0

for i in range(m):
    a[i], b[i] = map(int, input().split(" "))
    c.append( list(map(int, input().split(" "))))
    d.append(to_int(c[i]))
    #print("-----")
    for j in range(0,2**n):
        #print("{} {} {}".format(j, state[j], (j|d[i])))

        if state[j] != -1 and (state[j | d[i]] == -1 or state[j | d[i]] > state[j] + a[i]):
            state[j | d[i]] = state[j] + a[i]
    #print(state)
#print(d)
#print(state)
print(state[2**n-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

N, M = map(int, input().split())
dp = [[INF] * (1<<N) for i in range(M+1)]
dp[0][0] = 0
for i in range(M):
    a, b = map(int, input().split())
    c = [int(x)-1 for x in input().split()]
    mask = 0
    for x in c:
        mask |= 1<<x
    for s in range(1<<N):
        dp[i+1][s] = min(dp[i+1][s], dp[i][s])
        dp[i+1][s|mask] = min(dp[i+1][s|mask], dp[i+1][s]+a)
ans = dp[M][(1<<N)-1] if dp[M][(1<<N)-1] != INF else -1
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]




def change(iter, org):
    return sum([org[i-1] for i in iter])

def main():
    n, m = LI()
    cs = []
    a_s = []
    b_s = []
    org = [2**i for i in range(n)]
    for i in range(m):
        a, b = LI()
        a_s.append(a)
        b_s.append(b)
        cs.append(change(LI(), org))

    mem = [[INF for i in range(2**n)] for i in range(m)]

    mem[0][0] = 0
    mem[0][cs[0]] = a_s[0]

    for i in range(1, m):
        mem[i][0] = 0
        for j in range(2**n):
            mem[i][j] = mem[i-1][j]
        for j in range(2**n):
            if mem[i-1][j] != INF:
                # print("MWM", i, j | cs[i], j, cs[i])

                mem[i][j | cs[i]] = min(a_s[i] + mem[i-1][j], mem[i][j | cs[i]])
                # print("NAN", a_s[i] + mem[i-1][j], mem[i-1][j | cs[i]], mem[i-1][j], a_s[i], mem[i][j | cs[i]])
        # print(mem[i][15])
    # print(mem)
    print(mem[-1][-1] if mem[-1][-1] != INF else "-1")



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getlist():
	return list(map(int, input().split()))
INF = float("inf")

#初期化
N, M = getlist()
L = [[INF]  * (2 ** N) for i in range(M + 1)]
for i in range(M + 1):
	L[i][0] = 0

#計算
for i in range(M):
	a, b = getlist()
	c = getlist()
	C = 0
	for j in c:
		C += 2 ** (j - 1)
	for j in range(2 ** N):
		if L[i][j] != INF:
			L[i + 1][j | C] = min(L[i + 1][j | C], L[i][j] + a)
			L[i + 1][j] = min(L[i + 1][j], L[i][j])

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

Submission status: Accepted

Solution code:
def main():

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

    s = set()
    d = dict()
    for i in range(M):
        a, b = map(int ,input().split())
        temp = list(map(int, input().split()))
        v = 0
        for j in range(b):
            s.add(temp[j])
            v |= 1 << temp[j]
        if v in d: d[v] = min(d[v], a)
        else: d[v] = a

    if(len(s) < N): return -1

    M = len(d)
    cur = dict()
    cur[0] = 0
    for g in d:
        temp = cur.copy()
        for v in temp:
            cost = d[g]
            u = v | g
            if u in cur: cur[u] = min(cur[u], cur[v] + cost)
            else: cur[u] = cur[v] + cost

    target = 0
    for i in range(1, N+1): target |= 1 << i
    return cur[target]


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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
t=[]
for i in range(m):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    d=0
    for i in c:
        d+=2**(i-1)
    t.append([a,d])
e=[float("INF")]*(2**n)
e[0]=0
for i,j in t:
    for h in range(2**n):
        e[h|j]=min(i+e[h],e[h|j])
print(e[-1] if e[-1]!=float("INF") else -1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=[]
for i in range(m):
  a,b=map(int,input().split())
  C=[int(i) for i in input().split()]
  x=0
  for c in C:
    x|=(1<<(c-1))
  A.append((a,x))
DP=[float("inf")]*(2**n)
DP[0]=0
for i in range(m):
  a,x=A[i]
  for j in range(2**n):

    DP[j|x]=min(DP[j|x],DP[j]+a)

print(-1 if DP[2**n-1]==float("inf") else DP[2**n-1])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

N,M = map(int,readline().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(x) for x in readline().split()))
    C.append(sum(1<<(int(x)-1) for  x in readline().split()))

A,B = np.array(AB,np.int64).T
C = np.array(C,np.int64)

INF = 10**18
dp = np.full(1<<N,INF,np.int64)
dp[0] = 0

for n in range(1<<N):
    target = n|C
    value = A
    I = np.lexsort((value,target))
    target = target[I]
    value = value[I]
    is_first_elem = np.ones(M,np.bool)
    is_first_elem[1:] = ~(target[:-1] == target[1:])
    target = target[is_first_elem]
    value = value[is_first_elem]
    dp[target] = np.minimum(dp[target],dp[n]+value)

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

Submission status: Accepted

Solution code:
import heapq as hq
inf = 10 ** 18

N, M = map(int, input().split())
n = 1 << N
dis = [inf] * n
que = []
key = []

for _ in range(M):
    a, _ = map(int, input().split())
    c = map(int, input().split())
    k = 0
    for x in c:
        k += 1 << (x-1)
    key.append((k, a))

dis[0] = 0
hq.heappush(que, (0, 0))

while que != []:
    # print(*dis)
    # print(que)
    d, v = hq.heappop(que)
    if d == dis[v]:
        for gain, cost in key:
            if not (gain & v) == gain:
                to = gain | v
                if dis[to] > d + cost:
                    dis[to] = d + cost
                    hq.heappush(que, (dis[to], to))
if dis[n-1] == inf:
    print(-1)
else:
    print(dis[n-1])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
MOD = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, M = LI()

a = []
b = []
c = []

for i in range(M):
    ai, bi = LI()
    ci = LI()
    a.append(ai)
    b.append(bi)
    c.append(ci)

dp = [[MOD] * (1 << N)]*(M+1)

for i in range(M+1):
    dp[i][0] = 0

for i in range(M):
    for j in range(1<<N):
        boxSets = 0
        for cij in c[i]:
            boxSets |= 1 << (cij - 1)
        dp[i][j | boxSets] = min(dp[i][j | boxSets], dp[i][j] + a[i])

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

Submission status: Accepted

Solution code:
n,m=[int(_) for _ in input().split()]
k=[]
for i in range(m):
    k.append([int(_) for _ in input().split()])
    k[-1].append([int(_) for _ in input().split()])
dp=[10**9 for _ in range(2**n)]
dp[0]=0
for i in range(m):
    id=0
    for j in range(k[i][1]):id+=2**(k[i][2][j]-1)
    for j in range(2**n):dp[j|id]=min(dp[j|id],dp[j]+k[i][0])
if dp[-1] == 10**9:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
import math

n,m = list(map(int, input().split()))
a = []
b = []
c = []
for i in range(m):
    u,v = list(map(int, input().split()))
    a.append(u)
    b.append(v)
    clist = list(map(int, input().split()))
    temp = 0
    for i in range(len(clist)):
        temp += 2**(clist[i]-1)
    c.append(temp)

#print(a)
#print(b)
#print(c)

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

dp[0][c[0]] = a[0]

for i in range(m):
    dp[i][0]=0
    
for i in range(m-1):
    for j in range(2**n):
        dp[i+1][j] = min(dp[i][j],dp[i+1][j])
        dp[i+1][j|c[i+1]] = min(dp[i+1][j|c[i+1]],dp[i][j]+a[i+1])
        #print(j,j|c[i+1])
    #print("i:",i+1)
    #print(dp[i])
    #print(dp[i+1])

#print()
#print(dp[m-1])



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

Submission status: Accepted

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

# DPテーブルを初期化
dp = [10**9] * 2**(N+1)  # dp[010100011010]: 状態010100011010に到達するための最小コスト
dp[0] = 0

# ループを回す
for i in range(M):
    a, b = map(int, input().split())
    c = [int(i) for i in input().split()]

    bit = 0
    for cb in c:
        bit += 2**(cb-1)

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

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

Submission status: Accepted

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

for i in range(m+1):
    dp[(1<<n)-1][i] = 0
#print(dp)

for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    S_c = 0
    for x in c:
        S_c += 1<<(x-1)
    #print(S_c)
    for s in range(1<<n):
        dp[s][i+1] = min(dp[s][i],a+dp[s | S_c][i],dp[s][i+1])

    #print(dp)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
a = [0] * M
keys = [0] * M
inf = 10 ** 12
for i in range(M):
    a[i], _ = map(int, input().split())
    c_list = list(map(int, input().split()))
    keys[i] = sum([2 ** j for j in range(N) if j + 1 in c_list])

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

# print(keys)

for i in range(M):  # use key i
    for j in range(2 ** N):
        # print(dp, j, keys[i], dp[j | keys[i]], dp[j], a[i])
        dp[j | keys[i]] = min(dp[j] + a[i], dp[j | keys[i]])

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

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, _ = map(int, input().split())
    key_set = set(map(int, input().split()))
    key_bin = 0
    for c in key_set:
        key_bin += (2**(c-1))
    keys.append([a, key_bin])


N_bin = 2**N
# i番目までのkeyで
dp = [[float('inf')]*N_bin for _ in range(2)]
dp[0][0] = 0
for key in range(M):  # 新加えるkey
    key_val, key_set = keys[key]
    for bit in range(N_bin):  # 加える前の状態
        dp[(key+1) % 2][bit] = min(dp[(key+1) %
                                      2][bit], dp[key % 2][bit])  # くわえない
        dp[(key+1) % 2][bit | key_set] = min(dp[(key+1) % 2][bit | key_set],
                                             dp[key % 2][bit]+key_val)  # 加える
ans = float('inf')
for c in range(2):
    ans = min(ans, dp[c][-1])
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
def get_dp(x):
    return sum([2**i for i in x])
a = []
c = []
d=set()
for j in range(m):
    a2, _ = [int(i) for i in input().split()]
    a.append(a2)
    temp=[int(i)-1 for i in input().split()]
    c.append(get_dp(temp))
    d |= set(temp)

if len(d) != n:
    print(-1)
    exit()


dp = [10**10] * (2 ** n)
dp[0] = 0
for i,m in zip(c,a):
    for j, k in enumerate(dp):
        if k != 10**10:
            l=j|i
            dp[l] = min(dp[l], k + m)
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)
import itertools

N,M = map(int,readline().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(x) for x in readline().split()))
    C.append(sum(1<<(int(x)-1) for  x in readline().split()))

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

for n,((a,b),c) in itertools.product(range(1<<N),zip(AB,C)):
    m = n|c
    x = dp[n]+a
    if dp[m] > x:
      dp[m] = x
      
answer = dp[-1]
if answer == INF:
    answer = -1
print(answer)