有点要注意是用printf将浮点数转化为整数时一定要强制转化下，否则也可以用%.0f输出
1 # include <iostream>
2 # include <cstdio>
3 # include <vector>
4 # include <cmath>
5 # include <cstring>
6 # include <algorithm>
7 bool used[50000];
8 int q[50000][3],s,e;
9 # define N 12
10 using namespace std;
11 vector<int> g[N];
12 vector<int> l[N];
13 void print(int res)
14 {
15
16 if(q[res][2]==-1) return;
17 print(q[res][2]);
18 int ps=q[q[res][2]][0]&((1<<11)-1),ns=q[res][0]&((1<<11)-1);
19 if(ps>ns)
20 printf("- Switch off light in room %.0f.\n",log(ps-ns)/log(2.0)+1e-6);//这里输出浮点数注意！
21 else if(ps<ns)
22 printf("- Switch on light in room %.0f.\n",log(ns-ps)/log(2)+1e-6);
23 else
24 printf("- Move to room %d.\n",q[res][0]>>11);
25 }
26 int main()
27 {
28 // freopen("ans.txt","w",stdout);
29 int n,d,s,c=1;
30 while(true)
31 {
32 scanf("%d%d%d",&n,&d,&s);
33 if(!n&&!d&&!s) break;
34 for(int i=1;i<=n;i++)
35 {
36 g[i].clear();
37 l[i].clear();
38
39 }
40 while(d--)
41 {
42 int u,v;
43 scanf("%d%d",&u,&v);
44 g[u].push_back(v);
45 g[v].push_back(u);
46 }
47 while(s--)
48 {
49 int u,v;
50 scanf("%d%d",&u,&v);
51 l[u].push_back(v);
52 }
53 for(int i=1;i<=n;i++)
54 {
55 sort(g[i].begin(),g[i].end());
56 sort(l[i].begin(),l[i].end());
57 }
58 s=e=-1;
59 e=0;
60 q[e][0]=(1<<11)|(1<<1);
61 q[e][1]=0;
62 q[e][2]=-1;
63 int res=-1;
64 memset(used,false,sizeof(used));
65 used[q[e][0]]=true;
66 while(s!=e&&res==-1)
67 {
68 int pos=q[++s][0],len=q[s][1];
69 if(pos==((n<<11)|(1<<n))) res=s;
70 int sta=pos&((1<<11)-1);
71 pos>>=11;
72 for(int i=0;i<g[pos].size();i++)
73 if(!used[(g[pos][i]<<11)|sta]&&(sta|(1<<g[pos][i]))==sta)
74 {
75 used[(g[pos][i]<<11)|sta]=true;
76 q[++e][0]=(g[pos][i]<<11)|sta;
77 q[e][1]=len+1;
78 q[e][2]=s;
79 }
80 for(int i=0;i<l[pos].size();i++)
81 if(l[pos][i]!=pos&&(sta|(1<<l[pos][i]))==sta&&!used[(pos<<11)|(sta-(1<<l[pos][i]))])
82 {
83 used[(pos<<11)|(sta-(1<<l[pos][i]))]=true;
84 q[++e][0]=(pos<<11)|(sta-(1<<l[pos][i]));
85 q[e][1]=len+1;
86 q[e][2]=s;
87 }
88 for(int i=0;i<l[pos].size();i++)
89 if((sta|(1<<l[pos][i]))!=sta&&!used[(pos<<11)|(sta|(1<<l[pos][i]))])
90 {
91 used[(pos<<11)|(sta|(1<<l[pos][i]))]=true;
92 q[++e][0]=(pos<<11)|(sta|(1<<l[pos][i]));
93 q[e][1]=len+1;
94 q[e][2]=s;
95 }
96
97 }
98 printf("Villa #%d\n",c++);
99 if(res==-1) printf("The problem cannot be solved.\n\n");
100 else
101 {
102 printf("The problem can be solved in %d steps:\n",q[res][1]);
103 print(res);
104 printf("\n");
105 }
106
107 }
108 return 0;
109 }
110