AOJ 0172 - Doctor's Research Rooms

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0172

解法

を状態として BFS．

今いる部屋の電気を消さないことと，電気を操作するのは部屋番号について昇順と指定されていることに注意． 

  1 #include <iostream>
  2 #include <sstream>
  3 #include <vector>
  4 #include <queue>
  5 #include <algorithm>
  6 using namespace std;
  7 
  8 int main()
  9 {
 10   int N, M;
 11   while (cin >> N >> M && N != 0) {
 12     vector<vector<int> > g(N);
 13     for (int i = 0; i < M; i++) {
 14       int s, t;
 15       cin >> s >> t;
 16       --s;  --t;
 17       g[s].push_back(t);
 18       g[t].push_back(s);
 19     }
 20     unsigned init = 0;
 21     for (int i = 0; i < N; i++) {
 22       int x;
 23       cin >> x;
 24       init |= (x<<i);
 25     }
 26     vector<vector<int> > switches(N);
 27     for (int i = 0; i < N; i++) {
 28       int k;
 29       cin >> k;
 30       for (int j = 0; j < k; j++) {
 31         int r;
 32         cin >> r;
 33         --r;
 34         switches[i].push_back(r);
 35       }
 36       sort(switches[i].begin(), switches[i].end());
 37     }
 38 
 39     queue<pair<int,unsigned> > q;
 40     static const int INF = 10000000;
 41     vector<vector<int> > dist(N, vector<int>(1<<N, INF));
 42     q.push(make_pair(0, init));
 43     dist[0][init] = 0;
 44     vector<vector<pair<int,unsigned> > > prev(N, vector<pair<int,unsigned> >(1<<N));
 45     while (!q.empty() && dist[N-1][1<<(N-1)] == INF) {
 46       int n = q.front().first;
 47       unsigned s = q.front().second;
 48       q.pop();
 49 
 50       for (vector<int>::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
 51         if (s & (1<<*it) && dist[n][s] + 1 < dist[*it][s]) {
 52           dist[*it][s] = dist[n][s] + 1;
 53           prev[*it][s] = make_pair(n, s);
 54           q.push(make_pair(*it, s));
 55         }
 56       }
 57 
 58       for (vector<int>::const_iterator it = switches[n].begin(); it != switches[n].end(); ++it) {
 59         if (*it != n) {
 60           unsigned t = s ^ (1<<*it);
 61           if (dist[n][s] + 1 < dist[n][t]) {
 62             dist[n][t] = dist[n][s] + 1;
 63             prev[n][t] = make_pair(n, s);
 64             q.push(make_pair(n, t));
 65           }
 66         }
 67       }
 68     }
 69     if (dist[N-1][1<<(N-1)] != INF) {
 70       cout << "You can go home in " << dist[N-1][1<<(N-1)] << " steps." << endl;
 71       int n = N-1;
 72       unsigned s = 1<<(N-1);
 73       vector<string> logs;
 74       for (int i = 0; i < dist[N-1][1<<(N-1)]; i++) {
 75         const int m = prev[n][s].first;
 76         const unsigned t = prev[n][s].second;
 77         ostringstream oss;
 78         if (n == m) {
 79           const unsigned u = s ^ t;
 80           int r;
 81           for (r = 0; r < N; r++) {
 82             if (u & (1<<r)) {
 83               break;
 84             }
 85           }
 86           oss << "Switch " << (s & (1<<r) ? "on" : "off") << " room " << r+1 << ".";
 87         } else {
 88           oss << "Move to room " << n+1 << ".";
 89         }
 90         logs.push_back(oss.str());
 91         n = m;
 92         s = t;
 93       }
 94       for (vector<string>::const_reverse_iterator it = logs.rbegin(); it != logs.rend(); ++it) {
 95         cout << *it << endl;
 96       }
 97     } else if (*min_element(dist[N-1].begin(), dist[N-1].end()) == INF) {
 98       cout << "Help me!" << endl;
 99     } else {
100       cout << "You can not switch off all lights." << endl;
101     }
102   }
103   return 0;
104 }
aoj/0172.cc