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 itertools

N,M = map(int, input().split())
A = []
C = []
comp = sum(1<<int(x) for x in range(N))
for m in range(M):
  a, b = map(int, input().split())
  A.append(a)
  c = list(map(int, input().split()))
  C.append(sum(1<<(int(x)-1) for x in c))

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return

# B


def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return

# C


def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return

# D


def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    # go = g
    # myset = set([1])
    sq = int(sqrt(g)) + 2
    ans = 1

    for i in range(2, sq):
        if g % i == 0:
            ans += 1
        while g % i == 0:
            g /= i

            # myset.add(i)
        if g == 1:
            break
        if i == sq - 1:
            # myset.add(go)
            ans += 1

    print(ans)

    return

# E


def E():
    N, M = LI()
    bit_max = 1 << N
    dp = [[inf for i in range(bit_max)] for j in range(M+1)]
    dp[0][0] = 0

    for i in range(M):
        a, b = LI()

        c = LI()
        bit = 0

        for d in c:
            bit += 1 << (d-1)

        for w in range(bit_max):

            t = w | bit
            cost = dp[i][w] + a

            dp[i+1][t] = min(dp[i+1][t], cost)

            dp[i+1][w] = min(dp[i][w], dp[i+1][w])

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

    return

# F


def F():
    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)
    return


# Solve
if __name__ == '__main__':
    E()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return

# B


def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return

# C


def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return

# D


def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    # go = g
    # myset = set([1])
    sq = int(sqrt(g)) + 2
    ans = 1

    for i in range(2, sq):
        if g % i == 0:
            ans += 1
        while g % i == 0:
            g /= i

            # myset.add(i)
        if g == 1:
            break
        if i == sq - 1:
            # myset.add(go)
            ans += 1

    print(ans)

    return

# E


def E():
    N, M = LI()

    value = [0] * M
    power = [0] * M
    for i in range(M):
        a, b = LI()
        value[i] = a
        c = LI()
        L = ['0'] * N
        for k in c:
            L[k-1] = '1'
        bin = ''.join(L)
        power[i] = int(bin, 2)
    bin = ''.join(list(['1'] * N))
    #dp = [[inf] * (int(bin, 2)+1)] * M
    dp = [[inf for i in range(int(bin, 2)+1)] for j in range(M+1)]
    dp[0][0] = 0

    # for x in range(int(bin, 2)+1):
    #dp[0][x] = 0
    for i in range(M):

        for w in range(int(bin, 2) + 1):

            t = w | power[i]
            cost = dp[i][w] + value[i]

            dp[i+1][t] = min(dp[i+1][t], cost)

            dp[i+1][w] = min(dp[i][w], dp[i+1][w])

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

    return

# F


def F():
    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)
    return


# Solve
if __name__ == '__main__':
    E()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]


mod = 1000000007
inf = float('INF')


def A():
    a = II()
    b = a//2
    p = b/a
    if a % 2:
        print(1-p)
    else:
        print(p)

    return

# B


def B():
    N, K = map(int, input().split())
    h = LI()
    count = 0

    for i in h:
        if i >= K:
            count += 1
        else:
            continue
    print(count)
    return

# C


def C():
    N = II()
    A = LI()
    J = [0] * N
    for i, n in enumerate(A):
        J[n-1] = i+1
    for s in J:
        print(s, end=" ")

    return

# D


def D():
    A, B = map(int, input().split())
    g = gcd(A, B)
    # go = g
    # myset = set([1])
    sq = int(sqrt(g)) + 2
    ans = 1

    for i in range(2, sq):
        if g % i == 0:
            ans += 1
        while g % i == 0:
            g /= i

            # myset.add(i)
        if g == 1:
            break
        if i == sq - 1:
            # myset.add(go)
            ans += 1

    print(ans)

    return

# E


def E():
    N, M = LI()

    value = [0] * M
    power = [0] * M
    for i in range(M):
        a, b = LI()
        value[i] = a
        c = LI()
        L = ['0'] * N
        for k in c:
            L[k - 1] = '1'
        bint = ''.join(L)
        power[i] = int(bint, 2)
    bint = ''.join(list(['1'] * N))
    dp = [inf] * (int(bint, 2)+1)
    t = 0
    cost = 0

    dp[0] = 0
    for s in range(int(bint, 2) + 1):
        for i in range(M):
            t = s | power[i]
            cost = dp[s] + value[i]
            dp[t] = min(dp[t], cost)
    print(-1) if(dp[-1] == inf) else print(dp[-1])

    return

# F


def F():
    return


# Solve
if __name__ == '__main__':
    E()

Submission status: Accepted

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

inf = 1e9+7
dp = [inf] * (1 << N)
dp[0] = 0

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

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

    mask = sum(1 << (c-1) for c in hako)

    for i in range(1 << N):
        if dp[i] + a < dp[i | mask]:
            dp[i | mask] = dp[i] + a

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

Submission status: Accepted

Solution code:
import numpy as np
N, M = list(map(int, input().split(" ")))
dp = [np.inf] * (1 << N)
dp[0] = 0
bits = set()
bits.add(0)

for i in range(M):
    val,b = list(map(int, input().split(" ")))
    opens = list(map(int, input().split(" ")))
        
    # OpensからBitへの変換
    keybits = 0
    for tmp in opens:
        keybits += 1 << tmp-1
    
    for prev in list(bits):
        target = prev | keybits
        dp[target] = min(dp[target], dp[prev]+val)
        bits.add(target)
    
print(dp[-1] if dp[-1] != np.inf else -1)

Submission status: Accepted

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

N, M = inpl()
P = 2**N
INF = 10**12
cost = [INF]*P
cost[0] = 0
for _ in range(M):
    a, b = inpl()
    c = inpl()
    k = 0
    for ci in c:
        k |= 1<<(ci-1)
    for i in range(P):
        new = i | k
        cost[new] = min(cost[new],cost[i]+a)

ans = cost[P-1]
if ans >= INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """2 3
10 1
1
15 1
2
30 2
1 2"""
        output = """25"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """12 1
100000 1
2"""
        output = """-1"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """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"""
        output = """69942"""
        self.assertIO(input, output)
def resolve():
    (N,M)=(int(i) for i in input().split())
    housekis=[]
    for i in range(M):
        (a,b)=(int(i) for i in input().split())
        ability=sum([2**(int(i)-1) for i in input().split()])
        housekis.append([a,ability])
    dpt=[[1<<29 for i in range(2**N)] for j in range(M+1)]
    dpt[0][0]=0
    for i in range(M):
        for j in range(2**N):

            dpt[i+1][j]=min(dpt[i][j],dpt[i+1][j])
            dpt[i+1][j | housekis[i][1]]=min(dpt[i+1][j | housekis[i][1]],housekis[i][0]+dpt[i][j])

    if dpt[-1][-1]==1<<29:
        print(-1)
    else:
        print(dpt[-1][-1])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())

dp = [float("inf")]*(1<<n)
dp[0] = 0
for _ in [0]*m:
    a,b = map(int,input().split())
    sc = 0
    for e in map(int,input().split()):
        sc += 1<<(e-1)
    
    for i in range(1<<n):
        dp[i|sc] = min(dp[i|sc],dp[i]+a)


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

Submission status: Accepted

Solution code:
n, m = [int(x) for x in input().split()]

INF = int(10e8 + 1)
dp = [INF] * (1 << n)
dp[0] = 0

for j in range(m):
    cost = int(input().split()[0])

    boxes = [int(x)-1 for x in input().split()]
    mask = 0

    mask = sum(1 << box for box in boxes)
    
    for i in range(1 << n):
        if dp[i] + cost < dp[i | mask]:
            dp[i | mask] = dp[i] + cost

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

Submission status: Accepted

Solution code:
import heapq
N,M=map(int,input().split())
a=[0 for i in range(M)]
c=[0 for i in range(M)]
for i in range(M):
    a[i],b=map(int,input().split())
    tmp=[int(i)-1 for i in input().split()]
    for j in tmp:
        c[i]+=2**j
edge=sorted([(a[i],c[i]) for i in range(M)])
q=[]
heapq.heappush(q,(0,0))
dist=[10**15 for i in range(2**N)]
dist[0]=0
while(len(q)!=0):
    prc,src=heapq.heappop(q)
    if dist[src]<prc:
        continue
    for e in edge:
        cost,nxt=e
        dest=nxt|src
        if dest==src:
            continue
        if dist[dest]>dist[src]+cost:
            dist[dest]=dist[src]+cost
            heapq.heappush(q,(dist[dest],dest))
ans=dist[-1]
if ans==10**15:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from math import isinf

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

a = [0 for _ in range(M + 1)]
k = [0 for _ in range(M + 1)]
for i in range(M):
    a_i, _ = map(int, input().split())
    a[i + 1] = a_i
    k_i = 0
    for c in map(int, input().split()):
        k_i = k_i | 2 ** (c - 1)
    k[i + 1] = k_i

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

for i in range(1, M + 1):
    for s in range(2 ** N):
        # i番目の鍵を使わない場合
        dp[i][s] = min(dp[i][s], dp[i - 1][s])
        # i番目の鍵を使う場合
        dp[i][s | k[i]] = min(dp[i][s | k[i]], dp[i - 1][s] + a[i])

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

Submission status: Accepted

Solution code:
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()))
  C.append(c)
#print(A)
#print(B)
#print(C)

INF = 10**9+7
dp = [INF for _ in range(1<<N)]
dp[0] = 0
for j in range(1<<N):
  for i in range(M):
    t = 0
    for c in C[i]:
      t |= 1<<(c-1)
    dp[j|t] = min(dp[j|t], dp[j] + A[i])
    #print(dp)

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

Submission status: Accepted

Solution code:
import itertools
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, ((a, b), c) in itertools.product(range(1 << N), zip(AB, C)):
    m = n | c
    x = dp[n]+a
    if dp[m] > x:
      dp[m] = x

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

Submission status: Accepted

Solution code:
INF=10**9
N,M=map(int,input().split())
L=[]
for i in range(M):
  a,b=map(int,input().split())
  l=[]
  l.append(a)
  l.append(b)
  c=list(map(int,input().split()))
  c_=0
  for j in c:
    c_+=2**(j-1)
  l.append(c_)
  L.append(l)

dp=[[INF] for _ in range(2**N)]
dp[0]=[0]
for i in range(2**N):
  dp[i]=min(dp[i])
  if dp[i]!=INF:
    for j in range(M):
      if i!=i|L[j][2]:
        dp[i|L[j][2]].append(dp[i]+L[j][0])
if dp[2**N-1]!=INF:
  print(dp[2**N-1])
else:
  print(-1)

Submission status: Accepted

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

#100011 ← 各桁の数字が宝の状態。1:open　0:close。これが配列のindexとなる。
#宝がn個あれば、2**nの状態がある。
#配列の値は、その状態にするまでにかかるコスト。
#最初は、すべての状態の値が無限。
#具体的な鍵を使う毎に、そのコストに変更されていく。
inf=int(1e10)
dp=[inf]*(2**n)

#利用した鍵を入れる
bits=set()

#000000状態(どの宝も空いていない状態)のコストは0
dp[0]=0
#状態0にするための鍵を入れる
bits.add(0)

for _ in range(m):
  cost,kind=map(int,input().split())
  
  key=list(map(int,input().split()))
  keyBit=0
  
  #鍵であけられる宝箱を2進数に変換
  for temp in key:
    keyBit+=2**(temp-1)
  
  #orを取る
  for item in list(bits):
    temp=item|keyBit
    dp[temp]=min(dp[temp],dp[item]+cost)
    bits.add(temp)

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

Submission status: Accepted

Solution code:
from subprocess import*
with open('e.cpp','w')as f:f.write(r"""
#include <bits/stdc++.h>
using namespace std;

const int maxs = 4096;
int dp[maxs];

int main() {
	memset(dp, 0x3f, 16384);
	dp[0] = 0;
	int n, m;
	cin >> n >> m;
	while (m--) {
		int a, b, s = 0;
		cin >> a >> b;
		while (b--) {
			int c;
			cin >> c;
			s ^= 1 << c - 1;
		}
		dp[s] = min(dp[s], a);
	}
	for (int i = 0; i != n; ++i) for (int all = (1 << n) - 1 ^ 1 << i, sub = all; sub; sub = sub - 1 & all)
		dp[sub] = min(dp[sub], dp[sub ^ 1 << i]);
	for (int s = 0; s != (1 << n); ++s) if (s != (s & -s))
		for (int t = s - 1 & s; t != s; t = t - 1 & s)
			dp[s] = min(dp[s], dp[t] + dp[s ^ t]);
	int mask = (1 << n) - 1;
	if (dp[mask] == 0x3f3f3f3f) dp[mask] = -1;
	cout << dp[mask] << endl;
}""")
call(('g++','e.cpp'))
call('./a.out')

Submission status: Accepted

Solution code:
n,m=[int(s) for s in input().split()]
key=[]
for i in range(m):
  cost,b=[int(s) for s in input().split()]
  op=0
  for i in input().split():
    op+=1<<(int(i)-1)
  key.append([cost,op])
N=2**n
dp=[[10**7 for _ in range(N)] for _ in range(m)]
dp[0][key[0][1]]=key[0][0]
dp[0][0]=0
for i in range(1,m):
  for j in range(N):
    dp[i][j]=min([dp[i-1][j],dp[i][j]])
    x=j|key[i][1]
    dp[i][x]=min([dp[i][x],dp[i-1][j]+key[i][0]])
if dp[m-1][N-1]==10**7:
  print(-1)
else:
  print(dp[m-1][N-1])

Submission status: Accepted

Solution code:
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import heapq

import logging
logging.basicConfig(level=logging.DEBUG)

import sys
input = sys.stdin.readline

setrecursionlimit(1000000)

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

"""
## test data 
# input
5 5
10 2
1 3
15 2
2 4
5 2
3 5
20 1
5
20 4
1 2 3 4

# output
25
"""

def main():
    N,M=[int(x) for x in input().split()]
    dp = [INF] * 2**N
    dp[0]=0
    for i in range(M):
        a,b=[int(x) for x in 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[-1] if dp[-1]!=INF else -1)

main()

Submission status: Accepted

Solution code:
N, M = map(int,input().split())
dp = [float('inf')] * (2**N)
dp[0] = 0
for _ in range(M):
    a, b = map(int,input().split())
    c = sum(1 << (i-1) for i in map(int,input().split()))
    for x in range(2**N):
        if dp[c|x] > dp[x] + a:
            dp[c|x] = dp[x] + a
if dp[-1] == float('inf'):
    print(-1)
else:
    print(dp[-1])

Submission status: Accepted

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

def main():
    N, M = map(int,input().split())
    maxval = 10 ** (5 + 3 + 2)
    dp = [maxval] * (2 ** N)

    dp[0] = 0
    opened = set()
    opened.add(0)

    for Ki in range(M):
        a, b = map(int,input().split())
        c = 0
        clist = list(map(int,input().split()))
        for ci in clist:
            c |= 1 << (ci - 1)

        newopen = set()
        for op in opened:
            check = op | c
            chkval = dp[op] + a
            if dp[check] > chkval:
                dp[check] = chkval
                newopen.add(check)
            newopen.add(c)

        opened = opened | newopen
        
    ans = dp[-1]
    if ans == maxval:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from pprint import pprint
N, M = map(int, input().split())
A = [-1]*M
B = [-1]*M
C = [-1]*M

for i in range(M):
    A[i], B[i] = map(int, input().split())
    ls = list(map(int, input().split()))
    c = 0
    for j in range(len(ls)):
        c += 2 ** (ls[j]-1)
    C[i] = c


dp = [[float('inf')]*(2**N) for _ in range(M)]

j = 0
for i, di in enumerate(C):
    if i == 0:
        dp[i][di] = A[i]
        dp[i][0] = 0
        continue
    for j in range(2**N):
        stay = dp[i - 1][j | di]
        buy = dp[i - 1][j] + A[i]
        now = dp[i][j | di]
        dp[i][j | di] = min(stay, buy, now)
    for j in range(2**N):
        dp[i][j] = min(dp[i][j], dp[i-1][j])

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

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()

# (鍵の購入コスト, 開けられる宝箱)
keys = [None] * M
for i in range(M):
    c, _ = MAP()
    # どの宝箱を開けられるのかをbitで持っておく
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)

# dp[i][j] := i個目の鍵まで見て、集合jの宝箱を開けるための最小コスト
dp = list2d(2, 1<<N, INF)
dp[0][0] = 0
for i in range(M):
    # 今回の鍵で開けられる宝箱の集合s
    s = keys[i][1]
    c = keys[i][0]
    cur = i % 2
    nxt = (i+1) % 2
    # 今回の鍵を買わない遷移
    dp[nxt] = dp[cur][:]
    for j in range(1<<N):
        if dp[cur][j] != INF:
            m = j | s
            # 買う遷移：遷移元の開けられる宝箱の集合j | 今回の鍵で開けられる宝箱の集合s
            dp[nxt][m] = min(dp[nxt][m], dp[cur][j]+c)
ans = dp[M%2][-1]

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

Submission status: Accepted

Solution code:
N, M = [int(v) for v in input().split(' ')]

a_array = []
b_array = []
c_array = []


for i in range(M):
    a, b = [int(v) for v in input().split(' ')]
    bit = 0
    for c in input().split(' '):
        bit |= 1 << (int(c) - 1)

    a_array.append(a)
    b_array.append(b)
    c_array.append(bit)

key = 0
for c in range(N):
    key |= (1 << c)

dp = [-1 for i in range(key+1)]
dp[0] = 0

for item in range(0, M):
    now = c_array[item]

    for bits in range(0, 1 << N):
        cost1 = dp[bits]
        if cost1 < 0:
            continue

        cost1 += a_array[item]
        cost = dp[bits | now]
        if cost < 0 or cost > cost1:
            dp[bits | now] = cost1
    
print(dp[key])

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()

# (鍵の購入コスト, 開けられる宝箱)
keys = [None] * M
for i in range(M):
    c, _ = MAP()
    # どの宝箱を開けられるのかをbitで持っておく
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)

# dp[i][j] := i個目の鍵まで見て、集合jの宝箱を開けるための最小コスト
dp = list2d(2, 1<<N, INF)
dp[0][0] = 0
cur = 0
nxt = 1
for i in range(M):
    # 今回の鍵で開けられる宝箱の集合s
    s = keys[i][1]
    c = keys[i][0]
    for j in range(1<<N):
        # 今回の鍵を買わない遷移
        dp[nxt][j] = min(dp[nxt][j], dp[cur][j])
        if dp[cur][j] != INF:
            m = j | s
            # 買う遷移：遷移元の開けられる宝箱の集合j | 今回の鍵で開けられる宝箱の集合s
            dp[nxt][m] = min(dp[nxt][m], dp[cur][j]+c)
    cur, nxt = nxt, cur
ans = dp[M%2][-1]

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

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()

# (鍵の購入コスト, 開けられる宝箱)
keys = [None] * M
for i in range(M):
    c, _ = MAP()
    # どの宝箱を開けられるのかをbitで持っておく
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)

# dp[i][j] := i個目の鍵まで見て、集合jの宝箱を開けるための最小コスト
dp = list2d(2, 1<<N, INF)
dp[0][0] = 0
for i in range(M):
    # 今回の鍵で開けられる宝箱の集合s
    s = keys[i][1]
    c = keys[i][0]
    cur = i % 2
    nxt = (i+1) % 2
    for j in range(1<<N):
        # 今回の鍵を買わない遷移
        dp[nxt][j] = min(dp[nxt][j], dp[cur][j])
        if dp[cur][j] != INF:
            m = j | s
            # 買う遷移：遷移元の開けられる宝箱の集合j | 今回の鍵で開けられる宝箱の集合s
            dp[nxt][m] = min(dp[nxt][m], dp[cur][j]+c)
ans = dp[M%2][-1]

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

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()

# (鍵の購入コスト, 開けられる宝箱)
keys = [None] * M
for i in range(M):
    c, _ = MAP()
    # どの宝箱を開けられるのかをbitで持っておく
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)

# dp[i][j] := i個目の鍵まで見て、集合jの宝箱を開けるための最小コスト
dp = list2d(2, 1<<N, INF)
dp[0][0] = 0
for i in range(M):
    # 今回の鍵で開けられる宝箱の集合s
    s = keys[i][1]
    c = keys[i][0]
    for j in range(1<<N):
        # 今回の鍵を買わない遷移
        dp[(i+1)%2][j] = min(dp[(i+1)%2][j], dp[i%2][j])
        if dp[i%2][j] != INF:
            m = j | s
            # 買う遷移：遷移元の開けられる宝箱の集合j | 今回の鍵で開けられる宝箱の集合s
            dp[(i+1)%2][m] = min(dp[(i+1)%2][m], dp[i%2][j]+c)
ans = dp[M%2][-1]

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

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()

# (鍵の購入コスト, 開けられる宝箱)
keys = [None] * M
for i in range(M):
    c, _ = MAP()
    # どの宝箱を開けられるのかをbitで持っておく
    s = 0
    for a in [a-1 for a in LIST()]:
        s += 1 << a
    keys[i] = (c, s)

# dp[i][j] := i個目の鍵まで見て、集合jの宝箱を開けるための最小コスト
dp = list2d(M+1, 1<<N, INF)
dp[0][0] = 0
for i in range(M):
    # 今回の鍵で開けられる宝箱の集合s
    s = keys[i][1]
    c = keys[i][0]
    for j in range(1<<N):
        # 今回の鍵を買わない遷移
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        if dp[i][j] != INF:
            m = j | s
            # 買う遷移：遷移元の開けられる宝箱の集合j | 今回の鍵で開けられる宝箱の集合s
            dp[i+1][m] = min(dp[i+1][m], dp[i][j]+c)
ans = dp[M][-1]

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