ABC190 E Magical Ornament
まず, $ K \leq 17という特殊な制約に注目する. すると, bitDPという解法が思いつく. $ dp_{S, i} := 今の状態が$ Sで, 直前に$ i個の石を置いたときの必要な魔法石の個数の最小値 とする. すると遷移は指定された魔法石のうち元の集合に含まれる$ j, 含まれない$ iについて$ dp_{S | 2^i, i} = min(dp_{S | 2^i, i}, dp_{S, j} + cost_{j, i})とすればよく, あとは魔法石$ C_iから$ C_jを作るための最小コストを求めればよい. ここで$ N頂点$ M辺のすべての辺のコストが1のグラフを考えてみる. すると求めたいコストは頂点$ iから$ jまでの最短経路となる. すべての辺のコストが1ということより, BFSをすることによって求められる. 指定された魔法石について, これを前計算しておけばよい.