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:
n, m = map(int, input().split())
a, b, c = [], [], []

for i in range(m):
    a1, b1 = map(int, input().split())
    c1 = list(map(int, input().split()))
    a.append(a1)
    b.append(b1)
    c.append(c1)

#print(a, b, c)

def complete(keyIndice):
    boxSet = set()
    for i in range(len(keyIndice)):
        boxs = c[keyIndice[i]]
        for j in range(len(boxs)):
            boxSet.add(boxs[j])
    for i in range(1, n+1):
        if i not in boxSet:
            return False
    return True

def solve(start, keyIndice, cost):
    if complete(keyIndice):
        temp = 0
        for i in keyIndice:
            temp += a[i]
        return min(cost, temp)

    costs = []
    for i in range(start, m):
        if not i in keyIndice:
            temp = list(keyIndice)
            temp.append(i)
            cost += a[i]
            costs.append(solve(start+1, temp, cost))
    #print(costs)
    if len(costs) > 0:
        return min(costs)
    else:
        return 10**14

ans = solve(0, [], 10**10)
if ans == 10**14:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split()]
keys = {}
for i in range(M):
  keys[i] = []
  for j in range(2):
    if j == 0:
      n, m = [int(i) for i in input().split()]
      keys[i].append(n)
    else:
      op = set([int(i) for i in input().split()])
      keys[i].append(op)
 
memo = {}
def rec(i, opened):
  if len(opened) == N:
    return 0
  elif i == M:
    return float("inf")
  if i in memo and tuple(opened) in memo[i]:
    return memo[i][tuple(opened)]
  val1 = keys[i][0] + rec(i+1, opened | keys[i][1])
  val2 = rec(i+1, opened)
  val = min(val1, val2)
  if i not in memo:
    memo[i] = {}
  memo[i][tuple(opened)] = val
  return val
 
val = rec(0, set())
if val == float("inf"):
  print(-1)
else:
  print(val)

Submission status: Time Limit Exceeded

Solution code:
# TLE
import sys
sys.setrecursionlimit(100000)


def like_napsac(ite, price, box_set):
    if ite == M:
        if len(box_set) != N:
            return 10 ** 9
        else:
            return price
    elif box_set | key_box[ite] == box_set:
        return like_napsac(ite + 1, price, box_set)

    else:
        return min(like_napsac(ite + 1, price, box_set), like_napsac(ite+1, price+key[ite][0], box_set | key_box[ite]))


N, M = map(int, input().split())
key = [0] * M
key_box = [0]*M
for i in range(M):
    key[i] = [0] * 2
    key[i][0], key[i][1] = map(int, input().split())
    key_box[i] = set([int(x) for x in input().split()])
ans = like_napsac(0, 0, set())
if ans == 10 ** 9:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
openkey = []
keycanopen = []
keycost = []
for i in range(n + 1):
    # 何番麺のカギを使うと開けられるか
    openkey.append([])
for i in range(m):
    # そのカギは何を開けられるか
    keycanopen.append(None)
    keycost.append(-99999)

for i in range(m):
    a, b = map(int, input().split())
    keycanopen[i] = list(map(int, input().split()))
    keycost[i] = a
    for j in range(b):
        openkey[keycanopen[i][j]].append(i)

#print(openkey)
#print(keycanopen)
#print(keycost)
import copy

def tryopen (cur, openstatus, cost):
    #print("tryopen cur={0}, openstatus={1}, cost={2}".format(cur, openstatus, cost))
    if cur == n + 1:
        #print("CLEAR!")
        return cost
    elif openstatus[cur] == 1:
        # もう空いているなら次に
        return tryopen(cur + 1, openstatus, cost)
    else:
        nextcost = 10000000000
        #print("cur{0} can open key {1}".format(cur, openkey[cur]))
        costtmp = cost
        for nextkeyindex in openkey[cur]:
            #print("use key {0}".format(nextkeyindex))
            nextopenstatus = copy.deepcopy(openstatus)
            #print("prev{0}".format(nextopenstatus))
            for openbox in keycanopen[nextkeyindex]:
                # openboxが空けられる箱
                nextopenstatus[openbox] = 1
            #print("after{0}".format(nextopenstatus))
            # 次のboxを全部開けた
            nextcosttmp = tryopen(cur + 1, nextopenstatus, costtmp + keycost[nextkeyindex])
            nextcost = min(nextcost, nextcosttmp)
        return nextcost

res = tryopen(1, [0] * (n+1), 0)
if res == 10000000000:
    print(-1)
else:
    print(res)

Submission status: Time Limit Exceeded

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

keys = [0]*M  # [cost, openableset]
invdict = {i:set() for i in range(1,N+1)}

for mi in range(M):
  a,_ = map(int, input().strip().split(' '))
  c = set(map(int, input().strip().split(' ')))
  keys[mi] = [a,c]
  for box in c:
    invdict[box].add(mi)

essential_keys = set()
for k,v in invdict.items():
  if len(v) == 0:
    print(-1)
    exit()
  elif len(v) == 1:
    key_ = v.pop()
    essential_keys.add(key_)

cost = 0
openable = set()
for k in essential_keys:
  cost += keys[k][0]
  openable |= keys[k][1]


ans = float('inf')
mem = [[cost, essential_keys, openable]]  # [cost, keyset, openableset]
append = mem.append
while True:
  #print(mem)
  
  if len(mem) == 0: break;
  m = mem.pop()
  if m[0] >= ans: continue
  next_box = 1
  while next_box in m[2]:
    next_box += 1
  if next_box > N:
    ans = min(ans, m[0])
  elif next_box == N:
    nowcost = m[0] + min([keys[nk][0] for nk in invdict[next_box]])
    ans = min(ans, nowcost)
  else:
    for nk in invdict[next_box]:
      append([m[0]+keys[nk][0] , m[1]|{nk}, m[2]|keys[nk][1]])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
n, m = map(int, input().split())
keys = []
box = [[] for _ in range(n+1)]
for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    c = list(map(int, sys.stdin.readline().split()))
    keys.append([a, b, c])
    for j in c:
        box[j].append(i)


def deta(n, remain, price):
    if len(remain) == 0:
        return price
    res = -1
    r = copy.copy(remain)
    b = remain.pop()
    for k in box[b]:
        bn = copy.copy(remain)
        for nb in keys[k][2]:
            if nb in bn:
                bn.remove(nb)
        p = deta(n, bn, price + keys[k][0])
        if res == -1 or p < res:
            res = p
    return res

rem = set(range(1, n+1))
result = deta(n, rem, 0)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m = map(int, input().strip().split())
full_mask = 0
for i in range(n):
    full_mask |= 0b1 << i

key_costs = []
box = []
for i in range(m):
    a, b = map(int, input().strip().split())
    c = np.array(list(map(int, input().strip().split()))) - 1
    key_costs.append(a)
    box_mask = 0b0
    for i in c:
        box_mask |= 0b1 << i
    box.append(box_mask)

arr = [-2] * (1 << n)
arr[0] = 0
def calc_min_cost(mask, memo):
    if memo[mask] >= -1:
        return memo[mask]
    
    costs = []
    for idx in range(len(key_costs)):
        if mask & box[idx] == 0:
            continue
        submask = mask & ~box[idx]
        c = calc_min_cost(submask, memo)
        if c == -1:
            costs.append(-1)
        else:
            costs.append(key_costs[idx] + c)

    costs = np.array(costs)
    feasible_costs = costs[costs >= 0]
    if feasible_costs.size == 0:
        memo[mask] = -1
    else:
        memo[mask] = min(feasible_costs)
    
    return memo[mask]

print(calc_min_cost(full_mask, arr))

Submission status: Time Limit Exceeded

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

import itertools  
total = sum(a) + 1
#print(c)
for flags in itertools.product([0,1], repeat=M):
  temp = [x * y for (x, y) in zip(flags, c)]
  temp_a = [x * y for (x, y) in zip(flags, a)]
#  print(temp)
#  print(temp_a)
  temp_new = []
  for i in temp:
    for x in i:
      temp_new.append(x)
#  print(temp_new)
  
#  if sum(list(set(temp_new))) == (N+1) * N // 2:
  xxx = 0
  for i in range(1, N+1):
    if temp_new.count(i) > 0:
      xxx += i
#    print(5)
#  print(xxx)
  if total > sum(temp_a) and xxx == N*(N+1)//2 :
    total = sum(temp_a)
  
print(-1 if total == sum(a) + 1 else total)

Submission status: Time Limit Exceeded

Solution code:
import sys, copy
from collections import deque

input = sys.stdin.readline
N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
prices = [-1]*M
C = [[] for _ in range(M)]
for i in range(M):
  A,B = map(int,input().split())
  prices[i] = A
  for c in map(int,input().split()):
    C[i].append(c-1)
    graph[c-1].append(i)

queue = deque()
queue.append([[1]*N,0,])
ans = float('inf')
flag = False
while len(queue) != 0:
  prv_boxes, prv_prc = queue.pop()
  if sum(prv_boxes) == 0:
    ans=min(ans,prv_prc)
    flag = True
    continue
  if prv_prc >= ans: continue
  prv_box_i = prv_boxes.index(1)
  for key_i in graph[prv_box_i]:
    tmp_boxes = copy.deepcopy(prv_boxes)
    for box_i in C[key_i]:
      tmp_boxes[box_i] = 0      
    queue.append([tmp_boxes, prv_prc+prices[key_i]])
print(-1 if flag is False else ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC141e
import sys
import copy
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
kagi = []
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    kagi.append([a, b, c, i, 2**i])

memo = dict()


def dfs(pos, used, unlock, used2):
    if (memo.get((pos, used2))):
        # print('memo')
        return memo[(pos, used2)]
    if (len(unlock) == 0):
        #cost = 0
        # for i in used:
        #    cost += kagi[i][0]
        # return cost
        return 0
    if (pos >= m):
        return 10 ** 10
    # print(pos, used, unlock, copy.deepcopy(used), set().add(pos))
    no = copy.deepcopy(used)
    no2 = copy.deepcopy(unlock)
    if (len(set(kagi[pos][2]).intersection(unlock)) == 0):
        memo[(pos, used2)] = dfs(pos+1, no, no2, used2)
        return memo[(pos, used2)]
    yes = copy.deepcopy(used)
    yes.add(pos)
    yes2 = copy.deepcopy(unlock)
    yes2 -= set([i for i in kagi[pos][2]])

    # print(yes, yes2)
    memo[(pos, used2)] = min(dfs(pos+1, yes, yes2, used2+kagi[pos][4]) +
                             kagi[pos][0], dfs(pos+1, no, no2, used2))
    return memo[(pos, used2)]


ans = dfs(0, set(), set([i for i in range(1, n+1)]), 0)
print(ans if ans != 10 ** 10 else -1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a, b, c = [], [], []

for i in range(m):
    a1, b1 = map(int, input().split())
    c1 = list(map(int, input().split()))
    a.append(a1)
    b.append(b1)
    c.append(c1)

#print(a, b, c)

def complete(keyIndice):
    boxSet = set()
    for i in range(len(keyIndice)):
        boxs = c[keyIndice[i]]
        for j in range(len(boxs)):
            boxSet.add(boxs[j])
    for i in range(1, n+1):
        if i not in boxSet:
            return False
    return True

def solve(start, keyIndice, cost):
    if complete(keyIndice):
        temp = 0
        for i in keyIndice:
            temp += a[i]
        return min(cost, temp)

    costs = []
    for i in range(start, m):
        if not i in keyIndice:
            temp = list(keyIndice)
            temp.append(i)
            cost += a[i]
            costs.append(solve(start, temp, cost))
    #print(costs)
    if len(costs) > 0:
        return min(costs)
    else:
        return 10**14

ans = solve(0, [], 10**10)
if ans == 10**14:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

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

for _ in range(m):
    l2 = [int(i)for i in input().split()]+[[int(i)-1 for i in input().split()]]
    l.append([l2[0]/l2[1]]+l2)


l2 = [0 for i in range(n)]
for i in l:
    for j in i[3]:
        l2[j]=1
if 0 in l2:
    print(-1)
    exit()

l.sort(key=lambda x:x[0])
l2 = [0 for i in range(n)]
    
while(0 in l2):
    for i in range(m):
        tf = False
        for j in l[i][3]:
            if l2[j]==0:
                tf = True
        if tf:
            for j in l[i][3]:
                if l2[j] != 0:
                    l2 = [0 if i==l2[j] else i for i in l2]
                    break
                l2[j] = i+1
            else:
                continue
            break
cnt = 0
for i in list(set(l2)):
    cnt += l[i-1][1]
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

keys = [0]*M  # [cost, openableset]
invdict = {i:set() for i in range(1,N+1)}

for mi in range(M):
  a,_ = map(int, input().strip().split(' '))
  c = set(map(int, input().strip().split(' ')))
  keys[mi] = [a,c]
  for box in c:
    invdict[box].add(mi)

essential_keys = set()
for k,v in invdict.items():
  if len(v) == 0:
    print(-1)
    exit()
  elif len(v) == 1:
    key_ = v.pop()
    essential_keys.add(key_)

cost = 0
openable = set()
for k in essential_keys:
  cost += keys[k][0]
  openable |= keys[k][1]


ans = float('inf')
mem = deque()
mem.append([cost, essential_keys, openable])  # [cost, keyset, openableset]
while True:
  #print(mem)
  
  if len(mem) == 0: break;
  m = mem.popleft()
  if m[0] >= ans: continue
  next_box = 1
  while next_box in m[2]:
    next_box += 1
  if next_box > N:
    ans = min(ans, m[0])
  elif next_box == N:
    nowcost = m[0] + min([keys[nk][0] for nk in invdict[next_box]])
    ans = min(ans, nowcost)
  else:
    for nk in invdict[next_box]:
      mem.append([m[0]+keys[nk][0] , m[1]|{nk}, m[2]|keys[nk][1]])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a_b = []
c_li = []
ans_li = []

for i in range(m):
  a,b = map(int,input().split())
  a_b.append([a,b])
  c = list(map(int,input().split()))
  c_li.append(c)
for i in range(2**m):
  group = []
  total = 0
  for j in range(m):
    if((i>>j)&1):
      group = group + c_li[j]
      total += a_b[j][0]
  group = set(group)
  if len(group)==n:
    ans_li.append(total)
if len(ans_li) >0:
  print(min(ans_li))
else:
  print(-1)

Submission status: Time Limit Exceeded

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

keys = [0]*M  # [cost, openableset]
invdict = {i:set() for i in range(1,N+1)}

for mi in range(M):
  a,_ = map(int, input().strip().split(' '))
  c = set(map(int, input().strip().split(' ')))
  keys[mi] = [a,c]
  for box in c:
    invdict[box].add(mi)

essential_keys = set()
for k,v in invdict.items():
  if len(v) == 0:
    print(-1)
    exit()
  elif len(v) == 1:
    key_ = v.pop()
    essential_keys.add(key_)

cost = 0
openable = set()
for k in essential_keys:
  cost += keys[k][0]
  openable |= keys[k][1]


ans = float('inf')
mem = [[cost, essential_keys, openable]]  # [cost, keyset, openableset]
while True:
  #print(mem)
  
  if len(mem) == 0: break;
  m = mem.pop()
  if m[0] >= ans: continue
  next_box = 1
  while next_box in m[2]:
    next_box += 1
  if next_box > N:
    ans = min(ans, m[0])
  elif next_box == N:
    nowcost = m[0] + min([keys[nk][0] for nk in invdict[next_box]])
    ans = min(ans, nowcost)
  else:
    for nk in invdict[next_box]:
      mem.append([m[0]+keys[nk][0] , m[1]|{nk}, m[2]|keys[nk][1]])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC141e
import sys
import copy
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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


def dfs(pos, used, unlock):
    if (len(unlock) == 0):
        #cost = 0
        # for i in used:
        #    cost += kagi[i][0]
        # return cost
        return 0
    if (pos >= m):
        return 10 ** 10
    # print(pos, used, unlock, copy.deepcopy(used), set().add(pos))
    no = copy.deepcopy(used)
    no2 = copy.deepcopy(unlock)
    if (len(set(kagi[pos][2]).intersection(unlock)) == 0):
        return dfs(pos+1, no, no2)
    yes = copy.deepcopy(used)
    yes.add(pos)
    yes2 = copy.deepcopy(unlock)
    yes2 -= set([i for i in kagi[pos][2]])

    # print(yes, yes2)
    return min(dfs(pos+1, yes, yes2)+kagi[pos][0], dfs(pos+1, no, no2))


ans = dfs(0, set(), set([i for i in range(1, n+1)]))
print(ans if ans != 10 ** 10 else -1)

Submission status: Time Limit Exceeded

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

import sys
sys.setrecursionlimit(10000)

def readInts():
  return [int(s) for s in input().split(" ")]

def is_ok(opened):
  for b in opened:
    if not b:
      return False
  return True

def dfs(N, M, Ks, m, opened, s):
  if m >= M:
    return -1

  a, b, c = Ks[m]
  found = False
  opened_next = opened[:]

  for i in c:
    if not opened[i-1]:
      found = True
      opened_next[i-1] = True

  # not use
  cost = dfs(N, M, Ks, m+1, opened, s)
  if not found:
    return cost

  # use
  cost_use = s + a
  if not is_ok(opened_next):
    cost_use = dfs(N, M, Ks, m+1, opened_next, s + a)

  if cost >= 0 and cost_use >=0:
    return min(cost, cost_use)
  elif cost < 0:
    return cost_use
  else:
    return cost

def main():
  N, M = readInts()
  Ks = []
  for m in range(M):
    a, b = readInts()
    c = readInts()
    Ks.append((a, b, c))

  opened = [False for _ in range(N)]
  print(dfs(N, M, Ks, 0, opened, 0))

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# ABC141e
import sys
import copy
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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


def dfs(pos, used, unlock):
    if (len(unlock) == 0):
        cost = 0
        for i in used:
            cost += kagi[i][0]
        return cost
    if (pos >= m):
        return 10 ** 10
    # print(pos, used, unlock, copy.deepcopy(used), set().add(pos))
    no = copy.deepcopy(used)
    no2 = copy.deepcopy(unlock)
    if (len(set(kagi[pos][2]).intersection(unlock)) == 0):
        return dfs(pos+1, no, no2)
    yes = copy.deepcopy(used)
    yes.add(pos)
    yes2 = copy.deepcopy(unlock)
    yes2 -= set([i for i in kagi[pos][2]])

    # print(yes, yes2)
    return min(dfs(pos+1, yes, yes2), dfs(pos+1, no, no2))


ans = dfs(0, set(), set([i for i in range(1, n+1)]))
print(ans if ans != 10 ** 10 else -1)

Submission status: Time Limit Exceeded

Solution code:
def dfs(cost,S,L,N):#L,Nは定数
    mn=10**10
    if len(S)==N:
        return cost
    for i in range(1,N+1):
        if i in S:
            continue
        else:
            for e in L:
                if i in e[1]:
                    mn=min(mn,dfs(cost+e[0],(S|e[1]),L,N))

    return mn
                    


def main():
    full=set(list(range(1,13)))
    k=set()
    
    N,M=map(int,input().split())
    A=[]
    L=[]
    for i in range(M):
        a,_=map(int,input().split())
        C=set(map(int,input().split()))
        k=k.union(C)
        L.append((a,C))

    L.sort(key=lambda x:x[0])

    if len(k)<N:#全部の宝を開けるだけのカギがない
        return -1


    return dfs(0,set(),L,N)
    

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)


def like_napsac(ite, price, box_set):
    if ite == M:
        if len(box_set) != N:
            return 10 ** 9
        else:
            return price
    else:
        return min(like_napsac(ite + 1, price, box_set), like_napsac(ite+1, price+key[ite][0], box_set | key_box[ite]))


N, M = map(int, input().split())
key = [0] * M
key_box = [0]*M
for i in range(M):
    key[i] = [0] * 2
    key[i][0], key[i][1] = map(int, input().split())
    key_box[i] = set([int(x) for x in input().split()])
ans = like_napsac(0, 0, set())
if ans == 10 ** 9:
    print(-1)
else:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():

    N, M = map(int, input().split())
    A = []

    s = set()
    for i in range(M):
        a, b = map(int ,input().split())
        temp = list(map(int, input().split()))
        for j in range(b): s.add(temp[j])
        A.append([a, temp])

    if(len(s) < N): return -1

    cur = dict()
    cur[0] = 0
    for i in range(M):
        temp = cur.copy()
        for v in temp:
            cost = A[i][0]
            u = v
            for j in A[i][1]:
                u |= 1 << j
            if u in cur: cur[u] = min(cur[u], cur[v] + cost)
            else: cur[u] = cur[v] + cost

    target = 0
    for i in range(1, N+1): target |= 1 << i
    return cur[target]


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

Submission status: Time Limit Exceeded

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

import itertools  
total = sum(a) + 1
#print(c)
for flags in itertools.product([0,1], repeat=M):
  temp = [x * y for (x, y) in zip(flags, c)]
  temp_a = [x * y for (x, y) in zip(flags, a)]
#  print(temp)
#  print(temp_a)
  temp_new = []
  for i in temp:
    for x in i:
      temp_new.append(x)
#  print(temp_new)
  
  if sum(list(set(temp_new))) == (N+1) * N // 2:
#    print(5)
    if total > sum(temp_a):
      total = sum(temp_a)
  
print(-1 if total == sum(a) + 1 else total)

Submission status: Time Limit Exceeded

Solution code:
# ABC141e
import sys
import copy
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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


def dfs(pos, used, unlock):
    if (len(unlock) == 0):
        cost = 0
        for i in used:
            cost += kagi[i][0]
        return cost
    if (pos >= m):
        return 10 ** 10
    #print(pos, used, unlock, copy.deepcopy(used), set().add(pos))
    yes = copy.deepcopy(used)
    yes.add(pos)
    yes2 = copy.deepcopy(unlock)
    yes2 -= set([i for i in kagi[pos][2]])
    no = copy.deepcopy(used)
    no2 = copy.deepcopy(unlock)
    #print(yes, yes2)
    return min(dfs(pos+1, yes, yes2), dfs(pos+1, no, no2))


ans = dfs(0, set(), set([i for i in range(1, n+1)]))
print(ans if ans != 10 ** 10 else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
from copy import deepcopy, copy

import queue
from collections import deque



def divisor(n): #nの約数を全て求める
    i = 1
    table = set()
    while i * i <= n:
        if n%i == 0:
            table.add(i)
            table.add(n//i)
        i += 1
    return table

ans = 10 ** 10

def check(box_num, kagi_num, kagi_data, ind, now_data_kari, money, data):
    now_data = copy(now_data_kari)

    if ind == box_num:
        for i in range(box_num):
            if now_data[i] == 0:
                break
        else:
            global ans
            ans = min(ans, money)
        return


    if now_data[ind]:
        check(box_num, kagi_num, kagi_data, ind + 1, now_data, money, data)
        return

    check_set = set()
    for i in range(len(kagi_data[ind + 1])):
        aaa = kagi_data[ind + 1][i]
        now_data = copy(now_data_kari)

        bbb = ['0' for i in range(box_num)]
        flg = 1
        for ele in data[aaa][2]:
            if now_data[ele - 1] == 0:
                now_data[ele - 1] = 1
                flg = 0
            if ele >= ind + 1:
                bbb[ele - 1] = '1'
        if flg:
            continue
        bbb = ''.join(bbb)
        if bbb in check_set:
            continue
        check_set.add(bbb)
        check(box_num, kagi_num, kagi_data, ind + 1, now_data, money + data[aaa][0], data)



def main():
    box_num, kagi_num = map(int, input().split())

    data = [0 for i in range(kagi_num)]
    kari = set()



    for i in range(kagi_num):
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        kari |= set(b)
        data[i] = [a[0], a[1], b]

    data.sort(key=lambda x: x[0])

    kagi_data = defaultdict(list)
    for i in range(kagi_num):
        a = data[i]
        for ele in a[2]:
            kagi_data[ele].append(i)



    for i in range(1, box_num + 1):
        kagi_data[i] = list(kagi_data[i])
        kagi_data[i].sort()

    if len(kari) != box_num:
        print(-1)
        sys.exit()


    now_data = [0 for i in range(box_num)]
    check(box_num, kagi_num, kagi_data, 0, now_data, 0, data)

    global ans
    print(ans)




# def test():
#     for i in :
#         print(i)

if __name__ == '__main__':
    main()
    # test()

Submission status: Time Limit Exceeded

Solution code:

def main():
    cache = {}
    def solve(box, used, not_used):
        if len(box) == 0:
            return 0
        if box in cache:
            return cache[box]
        c = 10e10
        for k in not_used:
            ks = {k}
            m = solve(box - C[k], used or ks, not_used - ks)
            c = min(A[k]+m, c)
        cache[box] = c
        return c

    N, M = map(int, input().split())
    A, B, C = [None]*(M+1), [None]*(M+1), [None]*(M+1)
    Z = set()
    for i in range(M):
        A[i+1], B[i+1] = map(int, input().split())
        C[i+1] = set([int(x) for x in input().split()])
        Z.update(C[i+1])
    if len(Z) < N:
        return -1

    c = solve(frozenset(range(1,N+1)), set(), set(range(1,M+1)))
    if c >= 10e10:
        return -1
    return c

print(main())

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
a=[]
c=[]
for i in range(M):
  aa,bb=map(int,input().split())
  a.append(aa)
  cc=["0"]*(N+1)
  d=list(map(int,input().split()))
  for dd in d:
    cc[dd]="1"
  c.append(int("".join(cc[1:]),2))
#print(a)
#print(c)

X=[10**10]*2**N
X[0]=0
for i in range(2**N):
  if X[i]<10**10:
    for j in range(M):
      if i|c[j]<2**N:
        X[i|c[j]]=min(X[i|c[j]],X[i]+a[j])
print(X[2**N-1] if X[2**N-1]!=10**10 else -1)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
a=[]
c=[]
for i in range(M):
  aa,bb=map(int,input().split())
  a.append(aa)
  cc=["0"]*(N+1)
  d=list(map(int,input().split()))
  for dd in d:
    cc[dd]="1"
  c.append(int("".join(cc[1:]),2))
#print(a)
#print(c)

X=[10**10]*2**N
X[0]=0
for i in range(2**N):
  for j in range(M):
    if i|c[j]<2**N:
      X[i|c[j]]=min(X[i|c[j]],X[i]+a[j])
print(X[2**N-1] if X[2**N-1]!=10**10 else -1)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
from copy import deepcopy, copy

import queue
from collections import deque



def divisor(n): #nの約数を全て求める
    i = 1
    table = set()
    while i * i <= n:
        if n%i == 0:
            table.add(i)
            table.add(n//i)
        i += 1
    return table

ans = 10 ** 10

def check(box_num, kagi_num, kagi_data, ind, now_data_kari, money, data):
    now_data = copy(now_data_kari)

    if ind == box_num:
        for i in range(box_num):
            if now_data[i] == 0:
                break
        else:
            global ans
            ans = min(ans, money)
        return


    if now_data[ind]:
        check(box_num, kagi_num, kagi_data, ind + 1, now_data, money, data)
        return

    check_set = set()
    for i in range(len(kagi_data[ind + 1])):
        aaa = kagi_data[ind + 1][i]
        now_data = copy(now_data_kari)

        # if i != 0 and data[aaa][2][-1] == ind + 1:
        #     continue

        bbb = ['0' for i in range(box_num)]
        for ele in data[aaa][2]:
            now_data[ele - 1] += 1
            if ele >= ind + 1:
                bbb[ele - 1] = '1'
        bbb = ''.join(bbb)
        if bbb in check_set:
            continue
        check_set.add(bbb)
        check(box_num, kagi_num, kagi_data, ind + 1, now_data, money + data[aaa][0], data)



def main():
    box_num, kagi_num = map(int, input().split())

    data = [0 for i in range(kagi_num)]
    kari = set()



    for i in range(kagi_num):
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        kari |= set(b)
        data[i] = [a[0], a[1], b]

    data.sort(key=lambda x: x[0])

    kagi_data = defaultdict(list)
    for i in range(kagi_num):
        a = data[i]
        for ele in a[2]:
            kagi_data[ele].append(i)



    for i in range(1, box_num + 1):
        kagi_data[i] = list(kagi_data[i])
        kagi_data[i].sort()

    if len(kari) != box_num:
        print(-1)
        sys.exit()


    now_data = [0 for i in range(box_num)]
    check(box_num, kagi_num, kagi_data, 0, now_data, 0, data)

    global ans
    print(ans)




# def test():
#     for i in :
#         print(i)

if __name__ == '__main__':
    main()
    # test()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ps = [float('inf')] * 2**n
for _ in range(m):
    a, b = map(int, input().split())
    s = sum([2**(i - 1) for i in map(int, input().split())])
    ps[s] = min(ps[s], a)
    for i in range(2**n):
        if i == s:
            ps[i] = min(ps[i], ps[s])
        elif i & s == i:
            ps[i] = min(ps[i], ps[s])
        elif i & s == s:
            ps[s] = min(ps[i], ps[s])
        else:
            ps[i | s] = min(ps[i | s], ps[i] + ps[s])
if ps[2**n - 1] == float('inf'):
    print(-1)
else:
    print(ps[2**n - 1])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
N,M = map(int,input().split())
graph = {i:[] for i in range(N)}
prices = [-1]*M
for i in range(M):
  A,B = map(int,input().split())
  prices[i] = A
  for c in map(int,input().split()): graph[c-1].append(i)

queue = deque()
queue.append([0,-1,0])
ans_list = []
while len(queue) != 0:
  prv_box, prv_key, prv_prc = queue.pop()
  if prv_box == N:
    ans_list.append(prv_prc)
    continue
  if prv_key in graph[prv_box]:
    queue.append([prv_box+1, prv_key, prv_prc])
  else:
    for key in graph[prv_box]:
      queue.append([prv_box+1, key, prv_prc+prices[key]])
print(-1 if len(ans_list) == 0 else min(ans_list))