### 狗狗40题搞完纪念 » 1024

1024.cpp

```#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define BIN(i) (1 << (i))

const int MAXN = 10;
const int MASK = BIN(MAXN) - 1;

int main() {
int ri = 0, n, m, l, a, b;
vector<int> d[MAXN];
vector<int> s[MAXN];
int pre[MAXN][BIN(MAXN)];
int mind[MAXN][BIN(MAXN)];
int q[MAXN * BIN(MAXN)];

while (scanf("%d%d%d", &n, &m, &l) != EOF && n > 0) {
for (int i = 0; i < n; ++i) {
d[i].clear();
s[i].clear();
fill(mind[i], mind[i] + BIN(n), -1);
}
for (int i = 0; i < m; ++i) {
scanf("%d%d", &a, &b);
d[a - 1].push_back(b - 1);
d[b - 1].push_back(a - 1);
}
for (int i = 0; i < l; ++i) {
scanf("%d%d", &a, &b);
if (a != b) {
s[a - 1].push_back(b - 1);
}
}

mind[0][BIN(0)] = 0;
q[0] = (0 << MAXN) ^ BIN(0);
for (int begin = 0, end = 1; begin < end && mind[n - 1][BIN(n - 1)] == -1; ++begin) {
int x = q[begin] >> MAXN;
int y = q[begin] & MASK;
for (vector<int>::const_iterator i = d[x].begin(); i != d[x].end(); ++i) {
if ((y & BIN(*i)) != 0 && mind[*i][y] == -1) {
mind[*i][y] = mind[x][y] + 1;
pre[*i][y] = -1 - x;
q[end++] = (*i << MAXN) ^ y;
}
}
for (vector<int>::const_iterator i = s[x].begin(); i != s[x].end(); ++i) {
if (mind[x][y ^ BIN(*i)] == -1) {
mind[x][y ^ BIN(*i)] = mind[x][y] + 1;
pre[x][y ^ BIN(*i)] = *i;
q[end++] = (x << MAXN) ^ (y ^ BIN(*i));
}
}
}

printf("Villa #%d\n", ++ri);
if (mind[n - 1][BIN(n - 1)] == -1) {
puts("The problem cannot be solved.");
} else {
int x = n - 1, y = BIN(n - 1);
vector<int> ans(mind[x][y]);
printf("The problem can be solved in %d steps:\n", mind[n - 1][BIN(n - 1)]);
for (vector<int>::reverse_iterator i = ans.rbegin(); i != ans.rend(); ++i) {
if (pre[x][y] >= 0) {
*i = pre[x][y];
y ^= BIN(*i);
} else {
*i = -1 - x;
x = -1 - pre[x][y];
}
}
for (vector<int>::const_iterator i = ans.begin(); i != ans.end(); ++i) {
if (*i >= 0) {
printf("- Switch %s light in room %d.\n", (y & BIN(*i)) == 0 ? "on" : "off", *i + 1);
y ^= BIN(*i);
} else {
printf("- Move to room %d.\n", -*i);
x = -1 - *i;
}
}
}
puts("");
}

return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//290 	2010-06-27 06:03:25 	Accepted 	1024 	C++ 	0 	180 	anotherpeg 	Source
```