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
input = sys.stdin.readline

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

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

for i in range(m):
    a, b = map(int, input().split())
    c = sum(1<<(ci-1) for ci in map(int, input().split()))

    for j in range(1<<n):
        if dp[j] + a < dp[j | c]:
            dp[j | c] = dp[j] + a
        # dp[j | c] = min(dp[j] + a, dp[j | c])


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

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ab = []
d = [0 for _ in range(M)]
for i in range(M):
  ab.append(list(map(int, input().split())))
  for k in list(map(int, input().split())):
    d[i] += 2**(k-1)
  
infty = 10**8
  
dp = [infty for j in range(2**N)]
#i番目の鍵まで使って状態jにできる最小のコスト
dp[0] = 0

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ABC142E - Get Everything
import sys
input = sys.stdin.readline

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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()))
        #鍵mで開く宝箱を二進法で表記
        state = 0
        for c in C:
            state += 2**(c-1)

        #状態iに対して鍵mを使い、状態i|stateにいく場合と、元から入っている場合の大小を比較
        #状態i|state即ち状態iに対して鍵mを使った後の状態
        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"):
    #dp[-1]はdp[full-1]でも同じ
        return -1

    return dp[-1]

print(main())

Submission status: Accepted

Solution code:
# ABC142E - Get Everything
import sys
input = sys.stdin.readline

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
# ABC142E - Get Everything
import sys
input = sys.stdin.readline

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC142E - Get Everything
import sys
input = sys.stdin.readline

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC142E - Get Everything
import sys
input = sys.stdin.readline

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC142E - Get Everything
import sys
input = sys.stdin.readline

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# O(M + 4^N) 解
# 参考: https://twitter.com/ei1333/status/1177951676818325504

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

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

mod = 10**9 + 7

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

#################

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

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

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

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) #宝箱の集合bを開けるための最小コスト

vbs = [] #（最小コスト、宝箱の集合b）のリスト、ただしコストINFのものを除く
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:
#!/usr/bin/env python3
#ABC142 E

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC142 E

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(M):
    a,b=map(int,input().split())
    c=sum([1<<(i-1) for i in list(map(int,input().split()))])
#    print(a,b,c)
    for j in range(2**N):
        dp[j|c]=min(dp[j|c],dp[j]+a)
#    print(dp)

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
A = []
C = []
for i in range(m):
    ab = list(map(int,input().split()))
    A.append(ab)
    cc = list(map(int,input().split()))
    C.append(cc)
T = []
for i in range(m):
    t = 0
    for j in C[i]:
        t += 2**(j-1)
    T.append(t)


n2 = 2**n

DP = [[float("inf") for i in range(n2)] for j in range(m+1)]
for i in range(m+1):
    DP[i][0] = 0

for i in range(1,m+1):
    t = T[i-1]
    for j in range(n2):
        # print(i,j,t)
        # print(DP[i][j|t], DP[i-1][j|t], DP[i-1][j] + A[i-1][0])
        DP[i][j|t] = min(DP[i][j|t], DP[i-1][j|t], DP[i-1][j] + A[i-1][0])
        DP[i][j] = min(DP[i][j], DP[i-1][j])
        # print(DP[i][j|t])

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

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

C = 2 ** n
INF = 10 ** 6

dp = [[INF for _ in range(C)] for __ in range(m + 1)]
for i in range(m+1):
    dp[i][0] = 0

for i, ki in enumerate(k):
    for j in range(C):
        dp[i+1][j] = dp[i][j]
    for j in range(C):
        dp[i+1][j | ki[1]] = min(dp[i+1][j | ki[1]], dp[i][j] + ki[0])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

"""
bitDPというらしい
dp[i][j] = i番目の入力に対して、状態jを実現する最小値
j : 2^12通り。それぞれの宝箱をbitと見立てる
"""

N, M = map(int, input().split())
INF = 10**5+1


dp = [INF for i in range(2**N+1)]
dp[0] = 0

for i in range(M):
    cost,b = map(int, input().split())
    boxes = list(map(int, input().split()))
    status = 0
    for box in boxes:
        status += 2**(box-1)
    for j in range(2**N):
        if dp[j] != INF:
            nxt = status | j
            dp[nxt] = min(dp[j] + cost, dp[nxt])

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

# for i in range(M):
#     print(dp[i])

Submission status: Accepted

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

ab_list = []
c_list = []
for i in range(M):
    ab_list.append(list(map(int,input().split())))
    c_list.append(list(map(int,input().split())))
    
cost = [float("inf")]*(2**N)
cost[0] = 0

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

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

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

Submission status: Accepted

Solution code:
INF = 99999999999
n, m = map(int,input().split())
V = []
K = []
for _ in range(m):
    value, _ = map(int,input().split())
    V.append(value)
    tmp = [0] * n
    for i in map(int,input().split()):
        tmp[i-1] = 1
    tmp = int("".join(map(str, tmp)), 2)
    K.append(tmp)
dp = {}
import itertools
for flags in itertools.product([0,1], repeat=n):
    tmp = int("".join(map(str, list(flags))), 2)
    dp[tmp] = INF
for i in range(m):
    k = K[i]
    v = V[i]
    if v < dp[k]:
        dp[k] = v
    for dp_k, dp_v in dp.items():
        _k_sum = dp_k | k
        _v_sum = v + dp_v
        if _v_sum < dp[_k_sum]:
            dp[_k_sum] = _v_sum
_max = max(dp.keys())
if dp[_max] == INF:
    print(-1)
else:
    print(dp[_max])

Submission status: Accepted

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

INF = 10**12
N,M = map(int,input().split())
K = []
for i in range(M) :
    a,b = map(int,input().split())
    s = 0 #setをbitで管理.
    cx = list(map(int,input().split()))
    for c in cx :
        s = s | (1 << (c-1)) #setの和集合
    K.append([s, a])

#dp[bit]: 集合=bit のときのコストの最小値
dp = [INF]*(1 << N)
dp[0] = 0

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

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys

    input = sys.stdin.readline

    inf = (10 ** 5) * (10 ** 3)

    n, m = map(int, input().split())
    size = 1 << n

    dp = [inf] * size
    dp[0] = 0

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

        mask = 0
        for k in c:
            mask |= 1 << k

        for b in range(size - 1):
            if dp[b] == inf:
                continue
            nb = b | mask
            dp[nb] = min(dp[nb], dp[b] + cost)

    res = dp[size - 1]
    print(-1 if res == inf else res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
dp = [[float("inf")]*(2**N) for i in range(M+1)]
AC = []
ans = 0
for i in range(M):
    ai,bi = map(int,input().split())
    ci = list(map(int,input().split()))
    ci = sum([2**(i-1) for i in ci])
    AC.append([ai,ci])
for i in range(M+1):
    dp[i][0] = 0
for i in range(M):
    for j in range(2**N):
        if dp[i][j] != float("inf"):
            dp[i+1][j|AC[i][1]] = min(dp[i+1][j|AC[i][1]],dp[i][j]+AC[i][0]) 
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])

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

Submission status: Accepted

Solution code:
def main():
    import sys

    input = sys.stdin.readline

    inf = (10 ** 5) * (10 ** 3)

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

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

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

        mask = 0
        for k in c:
            mask |= 1 << k

        for b in range((1 << n) - 1):
            if dp[b] == inf:
                continue
            nb = b | mask
            dp[nb] = min(dp[nb], dp[b] + cost)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline


def main():
    INF = 10**9
    N, M = map(int, input().split())
    h = []
    dp = [INF for i in range(1 << N)]

    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
        h.append((a, s))

    dp[0] = 0

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
inf = float('inf')

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

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

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

    mask = 0
    for k in c:
        mask |= 1 << k

    for b in range((1 << n) - 1):
        nb = b | mask
        dp[nb] = min(dp[nb], dp[b] + cost)

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

Submission status: Accepted

Solution code:
def main():
  I=lambda:list(map(int,input().split()))
  n,m=I()
  e=[(I()[0],[1<<n-i for i in I()])for _ in'_'*m]
  I=9**9
  dp=[I]*2**n
  dp[0]=0
  for i,d in enumerate(dp):
    if d==I:continue
    for a,c in e:
      b,x=i,d+a
      for j in c:b|=j
      if dp[b]>x:dp[b]=x
  print(-(dp[-1]==I)or dp[-1])
main()

Submission status: Accepted

Solution code:
n, m = input().split(' ')
n = int(n)
m = int(m)
dp = [float('inf')]*(2**n)
dp[0] = 0
for i in range(m):
    a, b = input().split(' ')
    a = int(a)
    b = int(b)
    M = 0
    for j in input().split(' '):
        M += 2**(int(j)-1)

    for j in range(2**n):
        # dp[j|M] = min(dp[j]+a, dp[j|M])
        # dp[j|M] = dp[j] + a if dp[j] + a < dp[j|M] else dp[j|M]
        if dp[j] + a < dp[j|M]:
            dp[j|M] = dp[j] + a


print(dp[2**n-1] if dp[2**n-1] < float('inf') else -1)