JAG 夏合宿 2015 Day2 D: 真っ暗な部屋

問題

D: 真っ暗な部屋 - Japan Alumni Group Summer Camp 2015 Day 2 | AtCoder

解法

最初 M 人の人が、それぞれの暗い部屋にいるとする。これらの人たちを全員明るい部屋に連れていくことを考える。各状態について、遷移の仕方がk通りある。全員が暗い部屋にいる状態から、全員が明るい部屋にいる状態へ移動する、最短経路問題として考える。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N, M, K;
  cin >> N >> M >> K;
  vector<int> D(M);
  for (int i = 0; i < M; ++i) {
    cin >> D[i];
    D[i]--;
  }

  vector<int> darkness(N, -1);
  for (int i = 0; i < M; ++i) {
    darkness[D[i]] = i;
  }

  vector<vector<int>> v(N, vector<int>(K));
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < K; ++j) {
      cin >> v[i][j];
      v[i][j]--;
    }
  }

  vector<int> dist((1 << M), 1e9);
  queue<int> que;
  que.push((1 << M) - 1);
  dist[(1 << M) - 1] = 0;
  while (!que.empty()) {
    int now = que.front();
    que.pop();
    for (int k = 0; k < K; ++k) {
      int next_mask = 0;
      for (int m = 0; m < M; ++m) {
        if (now & (1 << m)) {
          int next = v[D[m]][k];
          if (darkness[next] < 0) continue;
          next_mask |= (1 << darkness[next]);
        }
      }
      if (dist[next_mask] > dist[now] + 1) {
        dist[next_mask] = dist[now] + 1;
        que.push(next_mask);
        if (next_mask == 0) {
          cout << dist[0] << endl;
          return 0;
        }
      }
    }
  }
}