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:
def solve_e(n, m, a_list, k_list):
    dp = [[10 ** 9] * (2 ** n) for _ in range(m + 1)]
    dp[0][0] = 0

    # update
    for i in range(m):
        k = k_list[i]
        for j in range(2 ** n):
            ll = (k ^ j) + ((k + j - (k ^ j)) // 2) - k
            dp[i + 1][j] = min(dp[i][j], dp[i][ll] + a_list[i])

    # print(dp)
    if dp[m][2 ** n - 1] == 10 ** 9:
        return -1
    else:
        return dp[m][2 ** n - 1]


def main():
    n, m = map(int, (input().split()))
    a_list = [0] * m
    k_list = [0] * m
    for i in range(m):
        a, b = map(int, (input().split()))
        a_list[i] = a
        c_list = list(map(int, (input().split())))
        k_list[i] = sum([2 ** (c - 1) for c in c_list])

    res = solve_e(n, m, a_list, k_list)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def solve():
    N, M = map(int, input().split())
    max_int = 2**32-1
    dp = [max_int]*2**N
    dp[0] = 0
    for i in range(M):
        a, b = map(int, input().split())
        d = sum(2**c for c in map(int, input().split()))>>1
        for j in range(2**N+1):
            if j|d == d:
                dp[j] = min(dp[j],a)
            elif j&d:
                dp[j] = min(dp[j], dp[j-(j&d)]+a)

    res = dp[-1] if dp[-1] < max_int else -1
    return str(res)

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

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    N, M = map(int, input().split())
    keys = []

    for _ in range(M):
        a, _ = map(int ,input().split())
        C = list(map(int, input().split()))
        cMask = 0
        for c in C:
            cMask |= (1 << (c - 1))
        keys.append((a, cMask))

    dp = [[INF] * (1 << N) for _ in range(M + 1)]  # dp[i][mask] = i番目の鍵までで，状態mask
    dp[0][0] = 0

    for i, (cost, cMask) in enumerate(keys, start=1):
        for mask in range(1 << N):
            dp[i][mask] = min(dp[i][mask], dp[i - 1][mask])
            dp[i][mask | cMask] = min(dp[i][mask | cMask], dp[i - 1][mask] + cost)

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

sol()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    from collections import defaultdict
    import itertools
    import copy
    
    N,M = map(int,input().split())
    dp = [[float("inf")]*(2**N) for i in range(M+1)]
    dp[0][0] = 0
    
    for i in range(1,M+1):
        #print(dp[M][(True,)*N])
        a,b = map(int,input().split())
        c = list(map(int,input().split()))
        tmp = 0
        for k in c:
            tmp += 2**(k-1)
        for j in range(2**N):
            now = j | tmp
            dp[i][j] = min(dp[i][j],dp[i-1][j])
            dp[i][now] = min(dp[i][now],dp[i-1][now], dp[i-1][j]+a)
            #print(dp[i][now],dp[i-1][now], dp[i-1][j]+a)
    
    if dp[M][2**N-1] == float("inf"):
        print(-1)
    else:
        print(dp[M][2**N-1])
            
    
    
main()

Submission status: Accepted

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


def main():
    N, M = map(int, input().split())
    
    N2 = 2**N
    X = [10**8+1]*N2
    X[0] = 0

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

        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 >= 10**8+1:
        ans = -1

    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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


n, m = [ int(v) for v in input().split() ]
n_q = 2**n

dp_list = [0] + [ 10**7 for i in range(n_q-1) ]
for i in range(m):
    a, b = [ int(v) for v in input().split() ]
    c_list = [ int(v)-1 for v in input().split() ]
    d = 0
    for j in c_list:
        d += 2**j
    for k in range(n_q):
        if 0 <= k | d < n_q:
            e = k | d
            if dp_list[e] > dp_list[k] + a:
                dp_list[e] = dp_list[k] + a

ans = dp_list[-1]
if dp_list[-1] == 10**7:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Keys = []
keys_set = set()

for m in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    c = [2 ** (ci - 1) for ci in c]
    Keys.append([a, sum(c)])
    keys_set |= set(c)


# 不可能判定
if len(keys_set) != N:
    print(-1)
    exit()


dp = [[float('inf')] * (2 ** N) for i in range(M + 1)]
for i in range(M + 1):
    dp[i][0] = 0

for i, (a, c) in enumerate(Keys):
    for bs in range(2 ** N):
        dp[i + 1][bs] = min(dp[i + 1][bs], dp[i][bs])
        dp[i + 1][bs | c] = min(dp[i][bs | c], dp[i + 1][bs | c], dp[i][bs] + a)

ans = float('inf')
for d in dp:
    ans = min(ans, d[-1])
print(ans)

Submission status: Accepted

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

N,M = map(int,input().split())
AB = [0]*M
C = [0]*M
for i in range(M):
    AB[i] = list(map(int,input().split()))
    C[i] = list(map(int,input().split()))

INF = 10**8
dp = [[INF]*(2**N) for _ in [0]*(M+1)]
dp[0][0] = 0

for i,ab in enumerate(AB):
    a,b = ab
    c = sum(1<<(d-1) for d in C[i])
    for t in range(2**N):
        dp[i+1][t] = min(dp[i+1][t],dp[i][t])
        dp[i+1][t|c] = min(dp[i+1][t|c],dp[i][t|c],dp[i][t]+a)
ans = dp[-1][-1]
if ans == INF : ans = -1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
INF=10**9
dp=[INF]*(2**n)
dp[0]=0
cost=[INF]*(2**n)
for i in range(m):
    a,b=map(int,input().split())
    c_list=list(map(int,input().split()))
    c=0
    for j in c_list:
        c+=2**(j-1)
    cost[c]=min(cost[c],a)
import itertools
ns=list(range(n))
for i in range(n):
    com=list(itertools.combinations(ns,i))
    for j in com:
        c=0
        for k in j:
            c+=2**k
        if not dp[c]==INF:
            for k in range(2**n):
                if not cost[k]==INF:
                    dp[c|k]=min(dp[c|k],dp[c]+cost[k])
if dp[2**n-1]==INF:
    print(-1)
else:
    print(dp[2**n-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)
from itertools import permutations

def solve(N, M, a, b, c):
    MAX = 2 ** N - 1
    INF = float('inf')
    dp = [INF] * (2 ** N)
    dp[0] = 0
    for i in range(M):
        bits = 0
        for j in c[i]:
            bits += (1 << (j - 1))
        for b in range(2 ** N):
            dp[b | bits] = min(dp[b | bits], dp[b] + a[i])
    if dp[MAX] < INF:
        print(dp[MAX])
    else:
        print(-1)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = []
    b = []
    c = []
    for i in range(M):
        A = int(next(tokens))  # type: int
        B = int(next(tokens))  # type: int
        a.append(A)
        b.append(B)
        c.append([ int(next(tokens)) for _ in range(B) ])
    solve(N, M, a, b, c)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys

    input = sys.stdin.readline

    inf = float('inf')

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

    dp = [inf] * (1 << n)
    dp[0] = 0

    for i in range(m):
        cost, _ = map(int, input().split())
        c = tuple(int(x) - 1 for x in input().rstrip().split())

        for mask in range((1 << n) - 1):
            if dp[mask] != inf:
                n_bit = mask
                for cc in c:
                    n_bit |= (1 << cc)
                dp[n_bit] = min(dp[n_bit], dp[mask] + cost)
                # print(bin(n_bit), dp[n_bit])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
tr = [ 10 ** 18 for _ in range(2**n) ]
tr[0] = 0
key = []
for _ in range(m):
  cost,b = map(int,input().split())
  raw = list(map(int,input().split()))
  get = 0
  for i in range(b):
    get += 2 ** (raw[i]-1)
  key.append([get,cost])
#print(key)
key.sort()
#print(key)
for j in range(2**n):
  for k in range(m):
    get,cost = key[k]
    tr[get | j] = min(tr[get | j],cost+tr[j])
    #print(tr,get,j,get | j)
    #print(get^j,get,j)
  #print(tr)
if tr[2**n-1] == 10 ** 18:
  print(-1)
else:
  print(tr[2**n-1])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint
sys.setrecursionlimit(2147483647)


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m = LI()
cost = [0 for _ in range(m)]
key_set = [0 for _ in range(m)]
for i in range(m):
    a, b = LI()
    cost[i] = a
    trs = LI()
    ret = 0
    for j in trs:
        ret += 1 << (j - 1)
    key_set[i] = ret





dp = [INF] * (2 ** n)
dp[0] = 0
for j in range(m):
    for k in range(2 ** n):
        dp[key_set[j] | k] = min(dp[k] + cost[j], dp[key_set[j] | k])



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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
inf = 1000000000
a = []
b = []
c = []
for i in range(m):
    aa,ba = map(int,input().split())
    ca = list(map(int,input().split()))
    k = 0
    for i in range(ba):
        k = k | (1 << ca[i]-1)
    a.append(aa)
    b.append(ba)
    c.append(k)

p = 2**n

dp = [[inf for i in range(p)] for i in range(m)]

for i in range(m):  
    dp[i][c[i]] = a[i]



for i in range(1,m):
    for j in range(p):
        ind = j | c[i]
        dp[i][ind] = min ( min(dp [i-1][j] + a[i], dp[i][ind]), dp[i-1][ind])
        dp[i][j] = min(dp[i][j], dp[i-1][j])

ans = dp[m-1][p-1]

if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    keys=[0]*m
    cost=[0]*m
    for i in range(m):
        a,b=map(int,input().split())
        cost[i]=a
        key=0
        for c in map(int,input().split()):
            key+=(1<<c-1)
        keys[i]=key
    N=2**n
    dp=[INF]*N
    dp[0]=0
    for k in range(N):
        for i in range(m):
            dp[k|keys[i]]=min(dp[k|keys[i]],dp[k]+cost[i])
    print(dp[N-1] if dp[N-1]!=INF else -1)
resolve()

Submission status: Accepted

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

key_prices = []
keys = []

for i in range(M):
	a, b = list(map(int, input().strip().split()))
	key_prices.append(a)
	bits = 0
	for c in input().strip().split():
		c = int(c) - 1
		bits += (2 ** c)
	keys.append(bits)

count = (2 ** N)
min_prices = [None] * count
min_prices[0] = 0

for price, key in zip(key_prices, keys):
	for bits in range(count):
		base_price = min_prices[bits]
		if base_price != None:
			new_bits = bits | key
			new_price = base_price + price
			old_price = min_prices[new_bits]
			if old_price == None or old_price > new_price:
				min_prices[new_bits] = new_price

min_price = min_prices[count - 1]
if min_price != None:
	print(min_price)
else:
	print("-1")

Submission status: Accepted

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

def main():
    n,m=map(int,input().split())
    Cost=[0]*m
    Key=[0]*m
    for i in range(m):
        a,b=map(int,input().split())
        C=tuple(map(int,input().split()))
        Cost[i]=a
        for c in C:
            Key[i]+=1<<(c-1)
    #print(Cost,Key)
    DP=[[float('inf')]*(1<<n) for _ in range(m+1)]
    for i,(c,k) in enumerate(zip(Cost,Key)):
        DP[i+1][k]=min(DP[i][k],c)
        for j in range(1,1<<n):
            DP[i+1][j]=min(DP[i][j],DP[i+1][j])
            DP[i+1][j|k]=min(DP[i+1][j|k],DP[i][j|k],DP[i][j]+c)
        #print(DP)
    print(-1 if DP[-1][-1]==float('inf') else DP[-1][-1])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from bisect import bisect_left

INF = 10**10
n, m = getList()

dp = [INF for i in range(1<<n)]
dp[0] = 0

for i in range(m):
    a, b = getList()
    cnums = getList()
    state = 0
    for cn in cnums:
        state += 1<<(cn-1)
    # print(state)
    for i, d in enumerate(dp):
        nstate = i | state
        # print(i, nstate, state)
        # print(dp[nstate] , dp[state])
        if dp[nstate] > dp[i] + a:
            dp[nstate] = dp[i] + a

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

Submission status: Accepted

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

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

for i in range(M):
    AB.append(list(map(int,input().split())))
    C.append(list(map(int,input().split())))
    
DP=[float("inf")]*((1<<N))
DP[0]=0
for i in range(M):
    for j in range(1<<N):
        bitscore=0
        for k in C[i]:
            bitscore+=(1<<(k-1))

        DP[j|bitscore]=min(DP[j]+AB[i][0],DP[j|bitscore])

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

Submission status: Accepted

Solution code:
inf = float('inf')

N, M = map(int,input().split())
A = []
C = []
for _ in range(M):
    a, b = map(int,input().split())
    A.append(a)
    c = list(map(int,input().split()))
    flag = 0
    for ci in c:
        flag |= 1 << (ci-1)
    C.append(flag)

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

for i in range(M):
    for S in range(1 << N):
        dp[i+1][S | C[i]] = min(dp[i+1][S | C[i]], dp[i][S] + A[i])
        dp[i+1][S] = min(dp[i+1][S], dp[i][S])

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

Submission status: Accepted

Solution code:
inf = 10**10
N, M = map(int, input().split())
A = []
B = []
C = []
for i in range(M):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    c = list(map(int, input().split()))
    res = 0
    for j in c:
        res+=(1<<(j-1))
    C.append(res)
dp = [[inf]*(2**N) for _ in range(M+1)]
dp[0][0] = 0
for i in range(1, M+1):
    for s in range(2**N):
        print
        dp[i][s] = min(dp[i-1][s], dp[i-1][(s|C[i-1])^C[i-1]]+A[i-1])
ans = dp[M][(1<<N)-1]
print(ans if ans<10**10 else -1)

Submission status: Accepted

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()



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

ab_list = []
c_list = []

for _ in range(M):
	ab_list.append(tuple(map(int, input().split())))
	c = tuple(map(int, input().split()))
	sum = 0
	for ci in c:
		sum += 2**(ci - 1)
	c_list.append(sum)

dp = [[10**10]*(2**N) for _ in range(M + 1)]

dp[0][0] = 0

for m in range(0, M):
	for i in range(2**N):
		if dp[m][0] < 10**10:
			loc_next = i | c_list[m]
			dp[m + 1][loc_next] = min(dp[m + 1][loc_next], dp[m][i] + ab_list[m][0])
			dp[m + 1][i] = min(dp[m + 1][i], dp[m][i])

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

Submission status: Accepted

Solution code:
INF = float('inf')
N,M = map(int,input().split())
A = []
B = []
C = []
for i in range(M):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    A.append(a)
    B.append(b)
    C.append(c)

dp = [{} for _ in range(M+1)]
for m in range(M):
    for i in range(2**N):
        if i == 0:
            dp[m][i] = 0
        else:
            dp[m][i] = INF

for m in range(M):
    a = A[m]
    b = B[m]
    c = C[m]
    s = 2**N-1
    for i in range(b):
        s -= 2**(c[i]-1)
    for i in range(2**N):
        dp[m+1][i] = min(dp[m][i],dp[m][i&s]+a)

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    #bitDP
    N,M = MI()
    money_box = []
    for i in range(M):
        a,_ = MI()
        c=LI()
        bit=0
        for d in c:
            bit += 1<<(d-1)
        money_box.append((a,bit))
    
    bit_max = 1<<N
    dp =[inf]*bit_max
    dp[0] = 0
    for bit_set in range(bit_max):
        for i,(money,bit) in enumerate(money_box):
            before = bit_set-(bit_set&bit)
            dp[bit_set] = min(dp[bit_set],dp[before]+money)
    ans = dp[-1]
    if dp[-1]==inf:
        print(-1)
    else:
        print(dp[-1])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
key = []
for _ in range(M):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    unlock = 0
    for i in range(1, N+1):
        if i in c:
            unlock += 2 ** (i-1)
    key.append((a, unlock))

dp = [[float('inf') for _ in range(2 ** N)] for _ in range(M + 1)]
dp[0][0] = 0
for i in range(M):
    for state in range(2 ** N):
        next_state = state | key[i][1]
        dp[i+1][next_state] = min(dp[i][state] + key[i][0], dp[i+1][next_state])
    for state in range(2 ** N):
        dp[i+1][state] = min(dp[i+1][state], dp[i][state])

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

Submission status: Accepted

Solution code:
from heapq import heappop,heappush
from operator import or_
from functools import reduce

N,M = map(int,input().split())
def it():
    for _ in range(M):
        a,b = map(int,input().split())
        c = sum(2**(x-1) for x in map(int,input().split()))
        yield (a,c)
boxes = list(it())

end = 2**N-1
check = reduce(or_, (c for a,c in boxes))
if check != end:
    print(-1)
    exit()

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

while q:
    c,v = heappop(q)
    if cost[v] < c:
        continue
    if v == end:
        break
    for nc,u in boxes:
        nc += c
        u |= v
        if nc < cost[u]:
            heappush(q,(nc,u))
            cost[u] = nc

print(cost[end])

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
res = [[] for i in range(m)]
val = [0] * m
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    for j in range(len(c)):
        res[i].append(c[j])
    val[i] = a



# i番目まで鍵を見たときにbit_stateの状態になっているときの最小値
INF = 10**9 + 7
dp  = [[INF]*(2**n) for i in range(m + 1)]
dp[0][0] = 0
for i in range(m):
    mask = 0
    for j in res[i]:
        mask += 2**(j-1)
    for bit_state in range(2**n):
        # i番目の鍵を使わない時
        dp[i+1][bit_state] = min(dp[i+1][bit_state], dp[i][bit_state])
        # i番目の鍵を使う時
        dp[i+1][bit_state | mask] = min(dp[i+1][bit_state | mask], dp[i][bit_state] + val[i])
if dp[-1][-1] == 10**9 + 7:
    print(-1)
else:
    print(dp[-1][-1])

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
dp = [0] + [1<<100] * ((1<<N)-1)
for _ in range(M):
    dppre = dp
    a, b = map(int, input().split())
    C = [int(a)-1 for a in input().split()]
    mask = sum([1<<C[i] for i in range(b)])
    for maskpre in range(1<<N):
        new = mask | maskpre
        dp[new] = min(dp[new], dppre[maskpre] + a)
        maskpre -= 1
print(dp[-1] if dp[-1] < (1<<100) else -1)

Submission status: Accepted

Solution code:

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

lis = [float("inf")] * (2 ** N)
lis[0] = 0

for i in range(M):

    a,b = map(int,input().split())

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

    num = 0
    for j in c:
        num += 2 ** (j-1)

    nlis = lis.copy()
    for j in range(2 ** N):

        if lis[j | num] > nlis[j] + a:
            lis[j | num] = nlis[j] + a

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

else:
    print (lis[2 ** N - 1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))

N, M = inpl()
size = 2**N
F = [2**i for i in range(12)]

DP = [10**18] * size
DP[0] = 0

for _ in range(M):
    a, b = inpl()
    X = sum([F[i-1] for i in inpl()])
    
    for i in range(size):
        DP[i|X] = min(DP[i|X], DP[i] + a)

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

Submission status: Accepted

Solution code:
N, M = [int(_) for _ in input().split()]
AS = []
for _ in range(M):
    a, _ = [int(_) for _ in input().split()]
    s = sum(1 << (c - 1) for c in [int(_) for _ in input().split()])
    AS += [(a, s)]
dp = [10**10] * (1 << N)
dp[0] = 0
for S in range(1 << N):
    for a, s in AS:
        dp[S | s] = min(dp[S | s], dp[S] + a)
if dp[-1] == 10**10:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))

# dp[i][p]: pの箱を開けられるときの最小コスト
dp = [[INF] * (1 << N) for _ in range(M + 1)]
for i in range(M):
    dp[i][0] = 0
for p in range(1 << N):
    dp[0][p] = 0

for i in range(1, M):
    a, b = list(map(int, sys.stdin.readline().split()))
    C = list(map(int, sys.stdin.readline().split()))

    pattern = 0
    for c in C:
        pattern += 1 << (c - 1)

    for p in range(len(dp[i])):
        dp[i + 1][p | pattern] = min(
            dp[i + 1][p | pattern],
            dp[i][p] + a
        )
        dp[i + 1][p] = min(
            dp[i + 1][p],
            dp[i][p]
        )

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

Submission status: Accepted

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

costs = [None for i in range(M)]
opens = [None for i in range(M)]

for i in range(M):
    costs[i] = list(map(int,input().split()))[0]
    o = list(map(int, input().split()))
    x = pow(2, 12)-1
    for item in o:
        x &= ~(1 << (item-1))
    opens[i] = x

dp = [-1 for i in range(pow(2, 12))]
dp[0] = 0

def recurse(required):
    if dp[required] != -1:
        return dp[required]

    totalCost = float('inf')
    for i in range(M):
        c = required & opens[i]
        if c == required:continue
        
        totalCost = min(totalCost, costs[i] + recurse(c))

    dp[required] = totalCost
    return totalCost


val = recurse(pow(2, N)-1)
if val == float('inf'):
    print(-1)
else:
    print(val)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[]
c=[]

for i in range(m):
    ab.append(list(map(int,input().split())))
    c.append(list(map(int,input().split())))
    
for i in range(m):
    temp=0
    for j in range(len(c[i])):
        temp+=2**(c[i][j]-1)
    c[i]=temp
    #c[i]=(("0"*n)+bin(temp)[2:])[-n:]
   
dp=dict()

for i in range(2**n):
    dp[i]=10**9
    #dp[(("0"*n)+bin(i)[2:])[-n:]]=-1
    
dp[0]=0
    
#print(dp)
for i in range(m):
    for k,item in dp.items():
        dp[c[i]|k]=min(dp[c[i]|k],dp[k]+ab[i][0])

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
l = [None] * m
li = [None] * m
for i in range(m):
    l[i] = list(map(int, input().split()))
    li[i] = list(map(int, input().split()))
dp = [[float('inf')] * (2 ** n) for _ in range(m + 1)]
dp[0][0] = 0
for i in range(m):
    for j in range(2 ** n):
        if dp[i][j] == float('inf'):
            continue
        tmp = j
        for x in li[i]:
            tmp |= 2 ** (x - 1)
        dp[i + 1][tmp] = min(dp[i + 1][j | tmp], dp[i][j] + l[i][0])
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
res = dp[m][2 ** n - 1]
if res == float('inf'):
    print(-1)
else:
    print(res)

Submission status: Accepted

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

A = []
C = []
for i in range(M):
    a,b = list(map(int,input().split()))
    c = list(map(int,input().split()))
    A.append(a)
    d = 0
    for j in range(b):
        d += pow(2, c[j]-1)
    C.append(d)

goal = pow(2, N)-1
e_list = [[] for i in range(goal+1)]
for i in range(goal+1):
    for j in range(M):
        e_list[i].append((i|C[j],A[j]))
#dijkstra
#you need to prepare e_list = [[orient,dist]]

import heapq
vi = 0
min_d_list = [10**27 for i in range(goal+1)]
min_d_list[vi] = 0
q = []
for i in range(N):
    heapq.heappush(q,[min_d_list[i],i])

while len(q)>0:
    d,v = heapq.heappop(q)
    for e in e_list[v]:
        v1,d1=e
        if min_d_list[v1]>d+d1:
            min_d_list[v1]=d+d1
            heapq.heappush(q,[d+d1,v1])

if min_d_list[goal]>=10**27:
    print(-1)
else:
    print(min_d_list[goal])

Submission status: Accepted

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

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 in range(1<<N):
    for (a,b),c in zip(AB,C):
        m = n|c
        dp[m] = min(dp[m],dp[n]+a)

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

Submission status: Accepted

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

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

ma = 1<<n
DP = [float("inf")]*ma
DP[0] = 0
for i in range(m):
    nxt = DP[::]
    a,b = map(int, input().split())
    mask = 0
    for c in map(int, input().split()):
        mask += 1<<(c-1)
    for j in range(ma):
        if nxt[j|mask] > DP[j] + a:
            nxt[j|mask] = DP[j] + a
    DP = nxt

ans = DP[-1]
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


n, m = li()
inf = float('inf')

a = []
b = []
c = []
for _ in range(m):
    ai, bi = li()
    ci = list(li_())
    a.append(ai)
    b.append(bi)
    state = 0
    for cij in ci:
        state += pow(2, cij)
    c.append(state)


dp = [inf]*(1<<n)
dp[0] = 0

for state in range(1<<n):
    for i in range(m):
        dp[state | c[i]] = min(dp[state] + a[i], dp[state | c[i]])

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())
e=[(int(input().split()[0]),list(map(int,input().split())))for _ in range(m)]
INF=10**18
dp=[INF]*2**n
dp[0]=0
for i in range(2**n):
    if dp[i]>=INF:continue
    for a,c in e:
        bit=i
        for j in c:
            bit|=2**(n-j)
        dp[bit]=min(dp[bit],dp[i]+a)
a=dp[-1]
if a>=INF:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    X = 2**N
    dp = [float("inf")] * X
    dp[0] = 0
    for i in range(M):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        bit = 0
        for item in c:
            bit |= 2**(item-1)
        for j in range(X):
            dp[j | bit] = min(dp[j | bit], dp[j] + a)
    if dp[X-1] == float("inf"):
        print(-1)
    else:
        print(dp[X-1])


if __name__ == "__main__":
    main()