abc 142 E - Get Everything (python)

自力AC。解説は dp しとるな。これが bitDP ってやつか？
制約が N=12 だったので bit 演算関係あるんかなと考えると、とりあえず入力される鍵を
例えば N=6 で 2 3 5 を開ける鍵だとすると、key1 = 2**(2-1)+2**(3-1)+2**(5-1)
とかはできるなあと思った。
これをすると嬉しいのが、key2 = 010011 (二進数表記) だとすると
key1 と key2 で開けれる宝箱の番号はbit演算で key1 or key2 (key1 | key2)
としたものを二進数表記したときに 1 となっている桁で表せる
あとは今作れる bit を set() で管理して、010011を作るのにかかる費用の最小値 mは
{010011:m}として dict に入れたら終わり。
求めるものは set() に 2**n-1 が入っているかどうか、入っているなら dict から最小値を出力する。
計算量は set() に入る種類が高々 2**n で操作が m 回あるので多分 O(m*2**n)
python で 1733ms, pypy で 320ms

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
c = set()
v = {}
for i in range(m):
  a,b = map(int,readline().split())
  d = list(map(int,readline().split()))
  e = 0
  for j in d:
    e += 2**(j-1)
  if i >= 1:
    s = list(c)
    for k in s:
      if not k|e in c:
        c.add(k|e)
        v[k|e] = a+v[k]
      else:
        v[k|e] = min(v[k|e],a+v[k])
  if not e in c:
    c.add(e)
    v[e] = a
  else:
    v[e] = min(v[e],a)
    
if 2**n-1 in c:
  print(v[2**n-1])
else:
  print(-1)