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:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = 10**11+1
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

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)

    # divisors.sort()
    return divisors


n,mm = m()
ke = set([i+1 for i in range(n)])
bo = [[] for i in range(n)]
dp = [Max for i in range(2**n)]
kkk = []
dp[0] = 0
waa = set()
for i in range(mm):
    a,b = m()
    c = l()
    bit = 0
    on = 0
    for i in c:
        bit |= 1 << (i-1)
    waa = waa | set(c)
    for j in range(2**n):
        dp[j|bit] = min(dp[j|bit] ,dp[j] + a)
    
kkk.sort(key = lambda x:x[1])
if ke != waa:
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  N, M = map(int, input().split())
  A = []
  C = []
  for _ in range(M):
      a, _ = map(int, input().split())
      A.append(a)
      C_ = list(map(int, input().split()))
      c = 0
      for c_ in C_:
          c |= 1<<c_-1
      C.append(c)
  dp = [float("inf")] * (1<<N)
  dp[0] = 0
  for a, c in zip(A, C):
      dp_new = dp[:]
      for s, d in enumerate(dp):
          dp_new[s|c] = min(d+a, dp_new[s|c])
      dp = dp_new
  #print(dp)
  ans = dp[(1<<N)-1]
  print(ans if ans != float("inf") else -1)

main()

Submission status: Accepted

Solution code:
def main():
    INF = float("inf")

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

    N2 = 2 ** N
    dp = [INF] * N2
    dp[0] = 0

    for _ in range(M):
        a, b = map(int, input().split())
        C = [int(i) for i in input().split()]
        mask = sum(1 << (c - 1) for c in C)
        for i in range(N2):
            if dp[i | mask] > dp[i] + a:
                dp[i | mask] = dp[i] + a

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    INF = float("inf")

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

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

    for _ in range(M):
        a, b = map(int, input().split())
        C = [int(i) for i in input().split()]
        mask = sum(1 << (c - 1) for c in C)
        for i in range(len(dp)):
            if dp[i | mask] > dp[i] + a:
                dp[i | mask] = dp[i] + a

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    INF = float("inf")

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

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

    for _ in range(M):
        a, b = map(int, input().split())
        C = [int(i) for i in input().split()]
        mask = sum(1 << (c - 1) for c in C)
        for i, dpi in enumerate(dp):
            if dp[i | mask] > dpi + a:
                dp[i | mask] = dpi + a

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
INF = float("inf")

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

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

for _ in range(M):
    a, b = map(int, input().split())
    C = [int(i) for i in input().split()]
    mask = sum(1 << (c - 1) for c in C)
    for i, dpi in enumerate(dp):
        if dp[i | mask] > dpi + a:
            dp[i | mask] = dpi + a

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
INF = 10 ** 12
T = [2**i for i in range(N)]
dp = [INF] * (2**N)
dp[0] = 0
for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    step = sum(T[c-1] for c in C)
    for j in range(2**N):
        dp[step|j] = min(dp[step|j], dp[j]+a)

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

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    full = 2**N
    dp = [float('inf')] * full
    dp[0] = 0
    for m in range(M):
        a, b = map(int, input().split())
        C = list(map(int, input().split()))
        state = 0
        for c in C:
            state += 2**(c-1)
        
        for i in range(full):
            if dp[i] != float('inf'):
                dp[i|state] = min(dp[i] + a, dp[i|state])
        
    
    if dp[-1] == float('inf'):
        return -1

    return dp[-1]

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

Submission status: Accepted

Solution code:
INF = float("inf")

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

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

for _ in range(M):
    a, b = map(int, input().split())
    C = [int(i) for i in input().split()]
    mask = sum(1 << (c - 1) for c in C)
    for i in range(len(dp)):
        if dp[i | mask] > dp[i] + a:
            dp[i | mask] = dp[i] + a

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

Submission status: Accepted

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

# dp[j] 箱の開封状態jのときの使用したお金の最小値

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

for i in range(M):
    ai, bi = map(int,input().split())
    cib = list(map(int,input().split()))
    bits = 0
    for ci in cib:
        bits |= 1 << (ci-1)
    for j in range(1<<N):
        dp[j|bits] = min(dp[j|bits], dp[j]+ai)

allbits = 0
for _ in range(N):
    allbits = 1 | allbits << 1
print(dp[allbits] if dp[allbits] != INF else -1)

Submission status: Accepted

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

def main():
    inf=float('inf')
    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)
    DP=[inf]*(1<<n)
    DP[0]=0
    for c,k in zip(Cost,Key):
        for i in range(1<<n):
            DP[i|k]=min(DP[i|k],DP[i]+c)
    print(-1 if DP[-1]==inf else DP[-1])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
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)
    DP=[[float('inf')]*(1<<n) for _ in range(m+1)]
    DP[0][0]=0
    for i,(c,k) in enumerate(zip(Cost,Key)):
        for j in range(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]+c)
    print(-1 if DP[-1][-1]==float('inf') else DP[-1][-1])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
n, m = map(int, input().split())
keys = []
box = [[] for _ in range(n+1)]

dr = 2**n
dp = [-1] * dr
dp[0] = 0

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    c = list(map(int, sys.stdin.readline().split()))
    k = 0
    for box in c:
        k += 1 << box-1
    for j in range(dr):
        if dp[j] != -1:
            price = dp[j] + a
            nex = j | k
            if dp [nex] == -1 or dp[nex] > price:
                dp[nex] = price

print(dp[dr-1])