4201:Switch Bulbs

問題文
https://icpcarchive.ecs.baylor.edu/external/42/4201.pdf

バルブを光らせるパターンが与えられるので、クエリで与えられるとおりにバルブを光らせるまでの最短手数を求めよ。

ビットDP。
dp[パターンのid][バルブの状態]:=最短手数
とすると、DAGの最短経路DPと同じようにできる。

光らせるパターンは整数にしておいて、ビットが立ってるとこだけを光らせるにはXORをとればよい。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#define INF (1<<29)
#define all(c) (c).begin(),(c).end()

using namespace std;

int dp[45][(1<<17)];

int main(void){

  int t;
  cin >> t;
  for(int tc=1;tc<=t;tc++){
    int n,m;
    cin >> n >> m;
    cout << "Case " << tc <<":"<<endl;
    vector<int>ptn(m);
    int a,b;
    fill(all(ptn),0);
    for(int i=0;i<m;i++){
      cin >> a;
      for(int j=0;j<a;j++){
        cin >> b;
        ptn[i]|=(1<<b);
      }
    }

    fill(dp[0],dp[45],INF);

    for(int i=0;i<45;i++)dp[i][0]=0;

    for(int i=0;i<m;i++){
      for(int S=0;S<(1<<n);S++){
        dp[i+1][S]=min(dp[i+1][S],dp[i][S]);
        dp[i+1][S^ptn[i]]=min(dp[i+1][S^ptn[i]],dp[i][S]+1);
      }
    }

    string s;
    int l;
    cin >> l;
    for(int i=0;i<l;i++){
      int g=0;
      cin >> s;
      reverse(all(s));
      for(int j=0;j<s.size();j++){
        g|=((s[j]=='1')<<j);
      }
      int ans=dp[m][g];
      if(ans>=INF)cout << -1 << endl;
      else cout << ans << endl;
    }
    cout << endl;
  }
  return 0;
}