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())
keys = []
for _ in range(M):
  a,b = map(int,input().split())

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

  keys.append((s, a))


# dp[i][j] = Nの状態の鍵を用いた時に、Mの鍵を開けるための最小コスト
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])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()

key_lis = []
key_cost = []

for _ in range(M):
	a, b = MAP()
	c = LIST()
	key = 0
	for x in c:
		key += 2**(x-1)
	key_lis.append(key)
	key_cost.append(a)


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

for S in range(1<<N):
	for i, key in enumerate(key_lis):
		dp[S|key] = min(dp[S|key], dp[S]+key_cost[i])

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
keys=[]
dp=[float("inf")]*pow(2,N)
dp[0]=0
for i in range(M):
    a,b=map(int,input().split())
    l=list(map(int,input().split()))
    num=0
    for j in l:
        num=num+pow(2,j-1)
    keys.append([a,num])
#print(keys)
for i in range(pow(2,N)):
    for j in range(M):
        dp[i|keys[j][1]]=min(dp[i|keys[j][1]],dp[i]+keys[j][0])
    #print(dp)
#print(dp)
if dp[pow(2,N)-1]==float("inf"):
    print(-1)
else:
    print(dp[pow(2,N)-1])

Submission status: Accepted

Solution code:
def min2(x,y):
    return x if x < y else y

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

large = 1<<20
dp = [large]*(1<<N + 1)
dp[0] = 0
data = []
for i in range(M):
    a, b = map(int, input().split())
    bit = 0
    for c in map(int, input().split()):
        c -= 1
        bit = bit|1<<c
    data.append((a, bit))
for i, x in enumerate(data):
    a, bit = x
    for p in range(1<<N):
        dp[p|bit] = min2(dp[p] + a, dp[p|bit])
print(dp[(1<<N)-1] if dp[(1<<N)-1] != large else -1)

Submission status: Accepted

Solution code:

N, M = map(int, input().split())
X = []
for i in range(M):
    a, _ = map(int, input().split())
    c = list(map(int, input().split()))
    key = sum(1 << (v - 1) for v in c)
    X.append([key, a])

INF = 10 ** 9 + 7
dp = [[INF] * (2 ** N) for _ in range(M + 1)]
dp[0][0] = 0
for i in range(M):
    for j in range(2 ** N):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        dp[i + 1][j | X[i][0]] = min(dp[i + 1][j | X[i][0]],
                                     dp[i][j] + X[i][1])

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

Submission status: Accepted

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

dp=[float("inf")]*g
dp[0]=0
for i in range(m):
    a,b=map(int,input().split())
    c_l=list(map(int,input().split()))
    f=0
    for c_i in c_l:
        f+=1<<(c_i-1)
    for j in range(g-1, -1, -1):
        dp[j|f]=min(dp[j]+a, dp[j|f])

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N, M = NMI()
    keys = {}
    for i in range(M):
        a, b = NMI()
        C = NLI()
        case = 0
        for c in C:
            case += 2**(c-1)
        keys[i+1] = (a, case)

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

    for key in range(0, M):
        for case in range(2**N):
            if dp[key][case] == 10**10:
                continue
            next_case = case | keys[key+1][1]
            dp[key+1][next_case] = min(dp[key][case] + keys[key+1][0], dp[key+1][next_case])
            dp[key+1][case] = min(dp[key][case], dp[key+1][case])
    ans = dp[M][2**N-1]
    print(ans if ans < 10**10 else -1)






if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, m = ns()
    d = []
    for _ in range(m):
        ai, bi = ns()
        ci = na()
        d.append([ai, bi, ci])

    # bit DP
    # dp[i] = iの各bitが1である番目の宝箱を開けられる状態となれる最小コスト
    dp = [INF for _ in range(2 ** n)]
    dp[0] = 0

    for ai, bi, ci in d:
        getkey = 0
        for cii in ci:
            cii -= 1
            getkey += 1 << cii

        for i in range(2 ** n):
            dp[i | getkey] = min(dp[i | getkey], dp[i] + ai)

    tmp = dp[2 ** n - 1]
    print(tmp if tmp != INF else -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]
    INF = 10**9


    N,M = LMIIS()
    keys = []
    for i in range(M):
        a,b = LMIIS()
        boxes = map(lambda x: int(x)-1, input().split())
        key = 0
        for b in boxes:
            key += 2**b
        keys.append((a,key))
        



    # 開けられる箱のパターン -> コスト
    dp = [INF] * 2 ** N
    dp[0] = 0

    for key_cost,key in keys:
        for box,cost in enumerate(dp):
            if cost != INF:
                dp[box|key] = min(dp[box|key], cost+key_cost)
    
    ans = dp[2**N-1]
    print(ans if ans != INF else -1)




    




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
dp = [0]*(2**n + 1)
for i in range(m):
  a,b = map(int, input().split())
  c = list(map(int, input().split()))
  temp=0
  for i in c:
    temp += 2 ** (i-1)
  for i in range(2**n):
    if i != 0 and dp[i] == 0:
      continue
    t = i | temp
    if dp[t] == 0:
      dp[t] = dp[i] + a
    else:
      dp[t] = min(dp[i] + a, dp[t])

ans = dp[2**n - 1]
if ans == 0:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
def resolve():
    N, M = list(map(int, input().split()))
    costs = []
    openables = []
    for i in range(M):
        a, b = list(map(int, input().split()))
        costs.append(a)
        C = list(map(int, input().split()))
        state = 0
        for c in C:
            state += (1<<(c-1))
        openables.append(state)
    
    dp = [[float("inf") for _ in range(4100)] for __ in range(10**3+100)]
    dp[0][0] = 0
    for i in range(M):
        for j in range(1<<N):
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            opened_boxes = openables[i]
            dp[i+1][j|opened_boxes] = min(dp[i+1][j|opened_boxes], dp[i][j]+costs[i])
    print(dp[M][(1<<N)-1] if dp[M][(1<<N)-1] < float("inf") else -1)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, M = LI()
    A = []
    C = []
    for i in range(M):
        a, _ = LI()
        bit = 0
        A.append(a)
        c = LI()
        for ix in c:
            bit = bit | 1 << (ix-1)
        C.append(bit)
    dp = [[inf for _ in range(1 << N)] for __ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        for j in range(1 << N):
            # use i-th key
            dp[i+1][j | C[i]] = min(dp[i+1][j | C[i]], dp[i][j] + A[i])
            dp[i+1][j] = min(dp[i+1][j], dp[i][j])
    ans = dp[M][(1 << N) - 1]
    if ans == inf:
        print(-1)
        return
    print(ans)
    return

main()

Submission status: Accepted

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

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

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

ans = dp[-1]

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

Submission status: Accepted

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

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

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

ans = dp[-1][-1]

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

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
a = [0]
b = [0]
c = [0]*(m+1)
for i in range(1, m+1):
    tab = list(map(int, input().split()))
    a.append(tab.pop(0))
    b.append(tab)
    tc1 = list(map(int, input().split()))
    tc2 = 0
    for j in tc1:
        tc2 |= 1<<(j-1)
    c[i] = tc2
INF = 10**9
dp = [[0] + [INF] * (2**n-1) for i in range(m+1)]
for i in range(1, m+1):
    for j in range(2**n):
        dp[i][j] = min(dp[i][j], dp[i-1][j])
        nj = j | c[i]
        dp[i][nj] = min(dp[i][nj], dp[i-1][nj], dp[i-1][j] + a[i])

print(-1) if dp[m][2**n-1] == INF else print(dp[m][2**n-1])

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()

BEST = [INF for i in range(1<<N)]
for i in range(M):
  c,m = IL()
  l = IL()
  b = 0
  for k in l: 
    b |= 1<<(k-1)
  for t in range(1<<N):
    BEST[t&b] = min(BEST[t&b],c)

@lru_cache(maxsize=None) 
def g(b):
  bits = []
  for i in range(N):
    if (b>>i)&1:
      bits.append(i)
  ret = []
  for k in range(1<<len(bits)):
    a = 0
    for j in range(len(bits)):
      if (k>>j)&1:
        a += 1<<bits[j]
    if count_bit(a)!=0 and count_bit(a)!=len(bits):
      ret.append(a)
  return ret
    
@lru_cache(maxsize=None) 
def f(b):
  if count_bit(b) == 1:
    return BEST[b]
  else: 
    return min(BEST[b],min(f(i)+f(b-i) for i in g(b)))
ans = f((1<<N)-1)
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()

BEST = [INF for i in range(1<<N)]
for i in range(M):
  c,m = IL()
  l = IL()
  b = 0
  for k in l: 
    b |= 1<<(k-1)
  for t in range(1<<N):
    BEST[t&b] = min(BEST[t&b],c)

@lru_cache(maxsize=None) 
def f(b):
  if count_bit(b) == 1:
    return BEST[b]
  else: 
    return min(BEST[b],min(f(b&i)+f(b-(b&i)) if (b&i!=b and b-(b&i)!=b) else INF for i in range(1<<N)))
ans = f((1<<N)-1)
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M = IL()

BEST = [INF for i in range(1<<N)]
for i in range(M):
  c,m = IL()
  l = IL()
  b = 0
  for k in l: 
    b |= 1<<(k-1)
  for t in range(1<<N):
    BEST[t&b] = min(BEST[t&b],c)

@lru_cache(maxsize=None) 
def f(b):
  if b == 0:
    return INF
  if count_bit(b) == 1:
    return BEST[b]
  else: 
    return min(BEST[b],min(f(b&i)+f(b-(b&i)) if (b&i!=b and b-(b&i)!=b) else INF for i in range(1<<N)))
ans = f((1<<N)-1)
if ans == INF:
  print(-1)
else:
  print(ans)

Submission status: Accepted

Solution code:
def main():
    n,m = tuple([int(t)for t in input().split()])

    keys = []

    dp = [10**9]*(1<<n)
    dp[0] = 0
    for _ in range(m):
        a,_ = tuple([int(t)for t in input().split()])
        c = tuple([int(t)for t in input().split()])
        key = 0
        for c_i in c:
            key |= 1<<(c_i-1)
        keys.append((a,key))
    

    for a,key in keys:
        for i in range(1<<n):
            dp[i|key] = min(dp[i|key],dp[i]+a)

    if dp[-1]==10**9:
        print(-1)
    else:
        print(dp[-1])
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n,m = tuple([int(t)for t in input().split()])

    keys = []

    dp = [10**9]*(1<<n)
    dp[0] = 0
    for _ in range(m):
        a,_ = tuple([int(t)for t in input().split()])
        c = tuple([int(t)for t in input().split()])
        key = 0
        for c_i in c:
            key |= 1<<(c_i-1)
        keys.append((a,key))
    

    for a,key in keys:
        for i in range(1<<n):
            dp[i|key] = min(dp[i|key],dp[i]+a)

    if dp[-1]==10**9:
        print(-1)
    else:
        print(dp[-1])
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def solve():
  ans = 0
  N, M = map(int, input().split())
  A,C = [0]*M,[0]*M
  for i in range(M):
    A[i],b = map(int, input().split())
    c = list(map(int, input().split()))
    for j in range(b):
      C[i] += 1<<(c[j]-1)
  dp = [float('inf')]*(1<<N)
  dp[0] = 0
  for i in range(1,(1<<N)+1):
    for key in range(M):
      if C[key] & i == 0:
        continue
      dp[i] = min(dp[i],dp[i&~C[key]]+A[key])
  ans = dp[-1]
  if ans==float('inf'):
    return -1
  return ans
print(solve())

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math
 
# import copy
from bisect import bisect_left, bisect_right
# import heapq
 
# sys.setrecursionlimit(1000000)
 
# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]
 
INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)
 

def makebin(arr):
    ret = 0
    for num in arr:
        ret += 2 ** (num - 1)

    return ret

def main():
    n, m = getList()
    dp = [INF] * (2 ** n)
    dp[0] = 0
    for i in range(m):
        a, b = getList()
        tgt = getList()
        kagi = makebin(tgt)
        for i, d in enumerate(dp):
            if d != -1:
                dp[i|kagi] = min(dp[i|kagi], d + a)
        # print(dp, kagi)

    if dp[-1] == INF:
        print(-1)
        return 
    print(dp[-1])
    # print(0&1)?






 
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

INF = 10 ** 9
dp = [INF] * (2 ** N)
dp[0] = 0
for i in range(M):
  a,b = map(int,readline().split())
  C = list(map(int,readline().split()))
  key = 0
  for c in C:
    key += (1 << (c - 1))
  for j in range(len(dp) - 1, -1, -1):
    if dp[j] == INF:
      continue
    if dp[j | key] > dp[j] + a:
      dp[j | key] = dp[j] + a

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

Submission status: Accepted

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

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

INF = 10 ** 9
dp = [INF] * (2 ** N)
dp[0] = 0
for i in range(M):
  a,b = map(int,readline().split())
  C = list(map(int,readline().split()))
  key = 0
  for c in C:
    key += (1 << (c - 1))
  for j in range(len(dp) - 1, -1, -1):
    if dp[j] == INF:
      continue
    dp[j | key] = min(dp[j | key], dp[j] + a)

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

Submission status: Accepted

Solution code:
import sys

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


def resolve():
    n, m = map(int, input().split())
    keys = []
    for _ in range(m):
        bit = ["0"] * n
        a, b = map(int, input().split())
        C = map(int, input().split())
        for c in C:
            bit[c - 1] = "1"
        bit = int("".join(bit), 2)
        keys.append([bit, a])

    dp = [f_inf] * (1 << n)
    dp[0] = 0
    for i in range(1 << n):
        for k, cost in keys:
            idx = i | k
            dp[idx] = min(dp[idx], dp[i] + cost)

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
INF = float("inf")


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

    dp = [INF] * (2 ** N)
    dp[0] = 0
    for s in range(2 ** N):
        for key, a in keys:
            t = s | key
            dp[t] = min(dp[t], dp[s] + a)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
bit = [int(1e18) for _ in range(1 << N)]
bit[0] = 0
F = {0}
for _ in range(M):
  a, b = map(int, input().split())
  c = list(map(int, input().split()))
  bas = 0
  for k in range(b):
    c[k] -= 1
    bas += (1 << c[k])
  L = [[j, bit[j]] for j in F]
  for j in L:
    tb = 0
    for k in range(N):
      tb += (((j[0] >> k) & 1) | ((bas >> k) & 1)) << k
    bit[tb] = min(bit[tb], j[1] + a)
    F.add(tb)
if bit[-1] != int(1e18):
  print(bit[-1])
else:
  print(-1)

Submission status: Accepted

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

abcsl = []
for _ in range(m):
    a,b = map(int, input().split())
    cl = list(map(int, input().split()))
    abcsl.append((a,b,cl))

# dp = [ [10**9]*(2**n) for _ in range(m) ]
dp = [10**9]*(2**n)
dp[0] = 0
for a,b,cl in abcsl:
    b_bit = 0
    for c in cl:
        b_bit += 2**(c-1)
    for i in range(2**n):
        dp[i|b_bit] = min(dp[i]+a, dp[i|b_bit])

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())
p = []
for k in range(m):  
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    key = 0
    for i in c:
        key += 2**(i-1)
    p.append([a,key])
inf = 10**9
dp = []
for u in range(m+1):
    dp.append([inf for i in range(2**n)])
dp[0][0] = 0
for i in range(m):
    for k in range(2**n):
        dp[i+1][k] = dp[i][k]
    for k in range(2**n):
        dp[i+1][k|p[i][1]] = min(dp[i][k|p[i][1]],dp[i][k]+p[i][0],dp[i+1][k|p[i][1]])
if dp[-1][-1] == inf:
    print(-1)
else:
    print(dp[-1][-1])