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: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
import math
import string
import collections
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = 10 ** 18
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M = map(int, input().split())
keys = []
for _ in range(M):
    a, b = map(int, input().split())
    bits = 0
    for i in map(int, input().split()):
        bits = bits | (1 << (i - 1))
    keys.append([a, bits])

dp = [[INF] * (2 ** N + 10) for _ in range(M + 10)]
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 | keys[i][1]] = min(dp[i + 1][j | keys[i][1]], dp[i][j] + keys[i][0])
print(dp[M][2 ** N - 1] if dp[M][2 ** N - 1] != INF else -1)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
dp = [float('inf')]*(1<<n)
dp[0] = 0
for _ in range(m):
    a,b = map(int,input().split())
    bit = 0
    for e in map(int,input().split()):
        bit += 1<<(e-1)
    for i in range(1<<n):
        dp[i|bit] = min(dp[i|bit], dp[i]+a)
if dp[-1] == float('inf'):
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

def main():
    N,M=map(int,input().split())
    key=[]
    for i in range(0,M):
        a,b=map(int,input().split())
        c=list(map(int,input().split()))
        s=sum(2**(c[j]-1) for j in range(0,b))
        key.append(s*(10**6)+a)


    node=2**N
    djk=Dijkstra(node)
    for i in range(0,M):
        s=key[i]//(10**6)
        a=key[i]%(10**6)
        for j in range(0,node):
            djk.add(j,s|j,a)

    d=djk.shortest_path(0)
    if d[node-1]==10**15:
        print(-1)
    else:
        print(d[node-1])


if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

def main():
    N,M=map(int,input().split())
    key=[]
    for i in range(0,M):
        a,b=map(int,input().split())
        c=list(map(int,input().split()))
        s=sum(2**(c[j]-1) for j in range(0,b))
        key.append(s*(10**6)+a)


    node=2**N
    djk=Dijkstra(node)
    for i in range(0,M):
        for j in range(0,node):
            s=key[i]//(10**6)
            a=key[i]%(10**6)
            djk.add(j,s|j,a)

    d=djk.shortest_path(0)
    if d[node-1]==10**15:
        print(-1)
    else:
        print(d[node-1])


if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

def main():
    N,M=map(int,input().split())
    key=[]
    for i in range(0,M):
        a,b=map(int,input().split())
        c=list(map(int,input().split()))
        s=sum(2**(c[j]-1) for j in range(0,b))
        key.append((s,a))


    node=2**N
    djk=Dijkstra(node)
    for i in range(0,M):
        for j in range(0,node):
            s,a=key[i]
            djk.add(j,s|j,a)

    d=djk.shortest_path(0)
    if d[node-1]==10**15:
        print(-1)
    else:
        print(d[node-1])

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

def main():
    N,M=map(int,input().split())
    key=[]
    for i in range(0,M):
        a,b=map(int,input().split())
        c=list(map(int,input().split()))
        s=sum(2**(c[j]-1) for j in range(0,b))
        key.append((s,a))


    node=2**N
    djk=Dijkstra(node)
    for i in range(0,M):
        for j in range(0,node):
            s,a=key[i]
            djk.add(j,s|j,a)

    d=djk.shortest_path(0)
    if d[node-1]==float('inf'):
        print(-1)
    else:
        print(d[node-1])

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

N,M=map(int,input().split())
key=[]
for i in range(0,M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    s=sum(2**(c[j]-1) for j in range(0,b))
    key.append([s,a])


node=2**N
djk=Dijkstra(node)
for i in range(0,M):
    for j in range(0,node):
        djk.add(j,key[i][0]|j,key[i][1])

d=djk.shortest_path(0)
if d[node-1]==float('inf'):
    print(-1)
else:
    print(d[node-1])

Submission status: Time Limit Exceeded

Solution code:
INF = 10**9
n, m = map(int, input().split())
keys = []
for _ in range(m):
    a, _ = map(int, input().split())
    c = 0
    for i in input().split():
        c += 2**(int(i)-1)
    keys.append((a, c))

dp = [INF]*(2**n)
dp[0] = 0
for a, c in keys:
    tmp = [INF]*(2**n)
    for j, d in enumerate(dp):
        if d == INF:
            continue
        tmp[j] = min(tmp[j], d)
        tmp[j|c] = min(tmp[j|c], d+a)
    dp = tmp

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

Submission status: Time Limit Exceeded

Solution code:
INF = 10**9
n, m = map(int, input().split())
keys = []
for _ in range(m):
    a, _ = map(int, input().split())
    c = 0
    for i in input().split():
        c += 2**(int(i)-1)
    keys.append((a, c))

dp = [INF]*(2**n)
dp[0] = 0
for a, c in keys:
    tmp = [INF]*(2**n)
    for j in range(2**n):
        if dp[j] == INF:
            continue
        tmp[j] = min(tmp[j], dp[j])
        tmp[j|c] = min(tmp[j|c], dp[j]+a)
    dp = tmp

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

Submission status: Time Limit Exceeded

Solution code:
INF = 10**9
n, m = map(int, input().split())
dp = [INF]*(2**n)
dp[0] = 0
for _ in range(m):
    a, _ = map(int, input().split())
    c = 0
    for i in input().split():
        c += 2**(int(i)-1)
    tmp = [INF]*(2**n)
    for j in range(2**n):
        tmp[j] = min(tmp[j], dp[j])
        tmp[j|c] = min(tmp[j|c], dp[j]+a)
    dp = tmp

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

Submission status: Time Limit Exceeded

Solution code:
INF = 10**9
n, m = map(int, input().split())
keys = []
for _ in range(m):
    a, _ = map(int, input().split())
    c = 0
    for i in input().split():
        c += 2**(int(i)-1)
    keys.append((a, c))

dp = [INF]*(2**n)
dp[0] = 0
for a, c in keys:
    tmp = [INF]*(2**n)
    for j in range(2**n):
        tmp[j] = min(tmp[j], dp[j])
        tmp[j|c] = min(tmp[j|c], dp[j]+a)
    dp = tmp

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000)
n, m = map(int, input().split())
keys = []
for _ in range(m):
    a, b = map(int, input().split())
    c = set(map(int, input().split()))
    keys.append((a, c))

ans = 10**7

def solve(i, cost, key_set):
    global ans
    if i==m:
        return
    tmp = key_set.copy()
    tmp |= keys[i][1]
    if len(tmp)==n:
        ans = min(ans, cost+keys[i][0])
    else:
        solve(i+1, cost+keys[i][0], tmp)
    solve(i+1, cost, key_set)

solve(0, 0, set())
print(ans if ans<10**7 else -1)

Submission status: Time Limit Exceeded

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

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

u = 1 << N
for i in range(M):
    a, b = map(int, input().split())
    c = sum(1 << (x - 1) for x in map(int, input().split()))

    for j in range(u):
        dp[c | j] = min(dp[c | j], dp[j] + a)


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

Submission status: Time Limit Exceeded

Solution code:
#142_E
n, m = map(int, input().split())
inf = 10 ** 10
keys = [0 for _ in range(m)]
A = [] 

for i in range(m):
    a, _ = map(int, input().split())
    keys[i] = sum([2 ** (int(c) - 1) for c in input().split()])
    A.append(a)
    
dp = [[inf for _ in range(2 ** n)] for _ in range(m+1)]
dp[0][0] = 0
for i in range(0, m):
    for key in range(2 ** n):
        dp[i+1][key] = dp[i][key]
        
    for key in range(2 ** n):
        dp[i+1][key | keys[i]] = min(dp[i+1][key | keys[i]],
                                     dp[i][key] + A[i])

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
l = []
for _ in range(m):
    a,b = map(int, input().split())
    cl = [x-1 for x in map(int, input().split())]
    b = 0
    for i in cl:
        b |= 1<<i
    l.append([a,b])

inf = 10**9
dp = [inf]*2**n
dp[0] = 0
for x in range(2**n):
    for i in range(m):
        a,b = l[i]
        dp[x|b] = min(dp[x|b], dp[x]+a)

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

Submission status: Time Limit Exceeded

Solution code:
# e get everything
n, m = map(int, input().split())

lists = []
for i in range(m):
    price, num = map(int, input().split())
    K = list(map(int, input().split()))
    cnt = 0
    for some in K:
        cnt += 2**(n - some)
    lists.append((price, cnt))

dp = [[10**10 for i in range(2**n)]for j in range(m + 1)]
# dp[i][j]=i番目までの鍵を使用してjの状態を再現するために必要な最小の値
dp[0][0] = 0
for i in range(1, m + 1):
    price, mode = lists[i - 1][0], lists[i - 1][1]
    for j in range(2**n):
        dp[i][j] = min(dp[i - 1][j], dp[i - 1][j &(2**n-1-mode)] + price)

ans = dp[m][2**n - 1]

if ans < 10**10:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
INF = float('INF')

def main():
    N, M = map(int, input().split())
    goal = 2 ** N - 1

    key_box = [None] * M
    suma = 0
    for i in range(M):
        a, b = map(int, input().split())
        openable = sum(map(lambda x: 2 ** (N- int(x)), input().split()))

        suma += a
        key_box[i] = (a, openable)

    dp = [INF] * (suma + 1)
    dp[0] = 0
    ans = INF

    for i in range(suma):
        if dp[i] == INF:
            continue

        for price, openable in key_box:

            if (i + price) > suma:
                continue

            next_openable = (dp[i] | openable)

            if next_openable == goal:
                ans = min(i + price, ans)

            if (dp[i + price] == INF) or (next_openable > dp[i + price]):
                dp[i + price] = next_openable

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
INF = float('INF')

def main():
    N, M = map(int, input().split())

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

        suma += a
        key_box[i] = (a, c)


    dp = [INF] * (suma + 1)
    dp[0] = []

    for i in range(suma):

        if dp[i] == INF:
            continue

        now_boxes = dp[i]
        for price, openable_box in key_box:
            next_price = i + price

            if next_price > suma:
                continue

            next_boxes = list(set(now_boxes + openable_box))

            if dp[next_price] == INF or (len(next_boxes) > len(dp[next_price])):
                dp[next_price] = next_boxes

    if len(dp[-1]) != N:
        print(-1)

    for i, box in enumerate(dp):

        if box == INF:
            continue

        if len(box) == N:
            print(i)
            break



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
# 参考1: https://drken1215.hatenablog.com/entry/2019/09/29/103500
# 参考2: https://www.slideshare.net/chokudai/wap-atcoder4


n, m = map(int, input().split())
A, B, C = [], [], []
for _ in range(m):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
    c = list(map(int, input().split()))
    now = 0
    for i in range(b-1, -1, -1):
        now += 2**(c[i]-1)
    C.append(now)

INF = 10**9
DP = [[INF for _ in range(2**n)] for _ in range(m+1)]
DP[0][0] = 0

for i in range(m):
    for j in range(2**n):
        c = C[i]
        # 鍵を使用しない
        DP[i+1][j] = min(DP[i][j], DP[i+1][j])
        # 鍵を使用する
        nex = j | c
        DP[i+1][nex] = min(DP[i+1][nex], DP[i][j]+A[i])

ans = 10**9
for i in range(m):
    ans = min(DP[i][-1], ans)

if ans == 10**9:
    ans = -1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
inf=10**9
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
dp=[[inf]*(2**n) for _ in range(m+1)]
def two(i):
	return "0"*(n-len(bin(i)[2:]))+bin(i)[2:]
for i in range(m+1):
	dp[i][0]=0
for i in range(m):
	a,b=map(int,input().split())
	r=0
	c=list(map(int,input().split()))
	for p in c:
		r+=2**(p-1)
	for j in range(2**n):
		x=j|r
		dp[i+1][x]=min(dp[i][j]+a,dp[i][x],dp[i+1][x])
	for j in range(2**n):
		dp[i+1][j]=min(dp[i+1][j],dp[i][j])
print(dp[-1][-1]) if dp[-1][-1]!=inf else print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

for i in range(M):
    a, b = MAP()
    c = LIST()
    d = 0
    # 1を立てる
    for x in c:
        # 1が存在するなら，dの一番最後，右から0番目，0シフト目に必要
        d += 1<<(x-1)
    for j in range(1<<N): # 2 ** N 列見る
#         # テーブルは一列ずつ見て更新しよう
        tmp = j|d
        dp[tmp] = min(dp[tmp], dp[j] + a)
if dp[-1] == INF:
    print(-1)
else:
    print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    INF=10**9
    n,m=map(int,input().split())
    key=[0]*m
    keycost=[0]*m

    for i in range(m):
        a,b=map(int,input().split())
        keycost[i]=a
        c=[pow(2,int(i)-1) for i in input().split()]
        key[i]=sum(c)
    
    dp=[[INF]*(m+1) for _ in range(1<<n)]
    dp[0]=[0]*(1+m)
    
    for s in range(1<<n):
        for i in range(m):
            dp[s][i+1]=min(dp[(s&key[i])^s][i]+keycost[i],dp[s][i])
    
    if dp[-1][m]==INF:
        print(-1)
    else:
        print(dp[-1][m])
 
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
A = [0] * M
B = [0] * M
C = []
for m in range(M):
    A[m], B[m] = map(int, input().split())
    C.append(set([int(cm) for cm in input().split()]))

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


def Set2Bit(st):
    bt = ["0"]*N
    for i in st:
        bt[i-1] = "1"
    return bt


for m in range(0, M):
    key = Set2Bit(C[m])
    key_bit = int("".join(key), 2)
    for bit in range(2**N):
        pre_bit = next_bit = bit
        dp[m+1][next_bit] = dp[m][pre_bit]
    for bit in range(2**N):
        pre_bit = bit
        next_bit = pre_bit | key_bit
        dp[m+1][next_bit] = min(dp[m+1][next_bit], dp[m][next_bit], dp[m][pre_bit] + A[m])

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

Submission status: Time Limit Exceeded

Solution code:
import itertools as itr

N, M = map(int, input().split())
A = [0] * M
B = [0] * M
C = []
for m in range(M):
    A[m], B[m] = map(int, input().split())
    C.append(set([int(cm) for cm in input().split()]))

INF = 100000000
dp = [[INF] * 2**N for _ in range(M + 1)]
for m in range(M + 1):
    dp[m][0] = 0


def Set2Bit(st):
    bt = ["0"]*N
    for i in st:
        bt[i-1] = "1"
    return bt


for m in range(0, M):
    key = Set2Bit(C[m])
    key_bit = int("".join(key), 2)
    for bit in itr.product("01", repeat=N):
        pre_bit = next_bit = int("".join(bit), 2)
        dp[m+1][next_bit] = dp[m][pre_bit]
    for bit in itr.product("01", repeat=N):
        pre_bit = int("".join(bit), 2)
        next_bit = pre_bit | key_bit
        dp[m+1][next_bit] = min(dp[m+1][next_bit], dp[m][next_bit], dp[m][pre_bit] + A[m])

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

Submission status: Time Limit Exceeded

Solution code:
import itertools as itr

N, M = map(int, input().split())
A = [0] * M
B = [0] * M
C = []
for m in range(M):
    A[m], B[m] = map(int, input().split())
    C.append(set([int(cm) for cm in input().split()]))

INF = (10**5) * (10**3)
dp = [[INF] * 2**N for _ in range(M + 1)]
for m in range(M + 1):
    dp[m][0] = 0


def Set2Bit(st):
    bt = ["0"]*N
    for i in st:
        bt[i-1] = "1"
    return bt


for m in range(0, M):
    key = Set2Bit(C[m])
    for bit in itr.product("01", repeat=N):
        pre_bit = next_bit = int("".join(bit), 2)
        dp[m+1][next_bit] = dp[m][pre_bit]
    for bit in itr.product("01", repeat=N):
        pre_bit = int("".join(bit), 2)
        key_bit = int("".join(key), 2)
        next_bit = pre_bit | key_bit
        dp[m+1][next_bit] = min(dp[m+1][next_bit], dp[m][next_bit], dp[m][pre_bit] + A[m])

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

Submission status: Time Limit Exceeded

Solution code:
import itertools as itr

N, M = map(int, input().split())
A = [0] * M
B = [0] * M
C = []
for m in range(M):
    A[m], B[m] = map(int, input().split())
    C.append(set([int(cm) for cm in input().split()]))

INF = (10**5) * (10**3)
dp = [[INF] * 2**N for _ in range(M + 1)]
for m in range(M + 1):
    dp[m][0] = 0


def Set2Bit(st):
    bt = ["0" for _ in range(N)]
    for i in st:
        bt[i-1] = "1"
    return bt


for m in range(0, M):
    key = Set2Bit(C[m])
    for bit in itr.product("01", repeat=N):
        pre_bit = next_bit = int("".join(bit), 2)
        dp[m+1][next_bit] = dp[m][pre_bit]
    for bit in itr.product("01", repeat=N):
        pre_bit = int("".join(bit), 2)
        key_bit = int("".join(key), 2)
        next_bit = pre_bit | key_bit
        dp[m+1][next_bit] = min(dp[m+1][next_bit], dp[m][next_bit], dp[m][pre_bit] + A[m])

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

Submission status: Time Limit Exceeded

Solution code:
import itertools as itr

N, M = map(int, input().split())
A = [0] * M
B = [0] * M
C = []
for m in range(M):
    A[m], B[m] = map(int, input().split())
    C.append(set([int(cm) for cm in input().split()]))

INF = (10**5) * (10**3)
dp = [[INF] * 2**N for _ in range(M + 1)]
for m in range(M + 1):
    dp[m][0] = 0


def Set2Bit(st):
    bt = ["0" for _ in range(N)]
    for i in st:
        bt[i-1] = "1"
    return bt


for m in range(0, M):
    for bit in itr.product("01", repeat=N):
        pre_bit = next_bit = int("".join(bit), 2)
        dp[m+1][next_bit] = dp[m][pre_bit]
    for bit in itr.product("01", repeat=N):
        pre_bit = int("".join(bit), 2)
        key_bit = int("".join(Set2Bit(C[m])), 2)
        next_bit = pre_bit | key_bit
        dp[m+1][next_bit] = min(dp[m+1][next_bit], dp[m][next_bit], dp[m][pre_bit] + A[m])

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

Submission status: Time Limit Exceeded

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

dp = [1e9 for _ in range(2**n)]
#dp[status]
# status : c1c2c3...を開けることができる=1としたときの2進⇒10進数(maxは1がnこ並ぶから2**n -1)
dp[0] = 0
for i in range(1,m+1):
  a, _ = list(map(int,input().split()))
  C = list(map(int,input().split()))
  s = sum([2**(c-1) for c in C]) ## 内包forできれいに書いてる
  for j in range(2**n): ## ひとつ前のステータスを総当たりでいく
    dp[j|s] = min(dp[j|s], dp[j] + a)  ## このorの書き方が美しいのか

ans = dp[2**n-1] # 全部のカギを使ったときのstatusがすべて1の時
print(ans if ans < 1e9 else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n, m = map(int,input().split())
a_list = []
c_list = []
for i in range(m):
    a, b = map(int, input().split())
    a_list.append(a)
    c = set(map(int, input().split()))
    c_list.append(c)


def solver(i, c):
    #i: number of keys checked. c: opened boxes (set). n boxes, m keys
    if i == m-1:
        if len(c) == n:
            return 0
        else:
            return INF
    if c_list[i+1].issubset(c):
        return solver(i+1, c)
    return min(solver(i+1, c.union(c_list[i+1]))+ a_list[i+1], solver(i+1, c))

if solver(-1, set()) > MOD:
    print(-1)
else:
    print(solver(-1, set()))