BFS,用位压缩..值得纪念的一题...
1 #include <iostream>
2 #include <string>
3 #include <algorithm>
4 #include <queue>
5 #include <vector>
6
7 using namespace std;
8 struct Node
9 {
10 int bplus;
11 int bminus;
12 int time;
13
14 int eplus;
15 int eminus;
16 Node(int bs=0,int bm=0,int t=0,int es=0,int em=0):bplus(bs),bminus(bm),time(t),eplus(es),eminus(es){};
17 bool operator<(const Node& c)const{
18 return time<c.time;
19 }
20 };
21 int hash[1050000];
22 struct ExNode
23 {
24 int num;
25 int time;
26 bool operator<(const ExNode& x)const{
27 return time>x.time;
28 }
29 ExNode(int n=0,int t=0):num(n),time(t){};
30 };
31 vector<Node> vec;
32 int n,m;
33 inline void Input()
34 {
35 memset(hash,-1,sizeof(hash));
36 int t;
37 string s1,s2;
38 vec.clear();
39 for(int i=0;i<m;i++){
40 cin>>t>>s1>>s2;
41 Node tmp;
42 tmp.time=t;
43 for(int j=0;j<s1.size();j++){
44 if(s1[j]=='+')tmp.bplus|=1<<(n-j-1);
45 else if(s1[j]=='-')tmp.bminus|=1<<(n-j-1);
46 }
47 for(int j=0;j<s2.size();j++){
48 if(s2[j]=='+')tmp.eplus|=1<<(n-j-1);
49 else if(s2[j]=='-')tmp.eminus|=1<<(n-j-1);
50 }
51 vec.push_back(tmp);
52 }
53 sort(vec.begin(),vec.end());
54 }
55 bool BFS()
56 {
57 priority_queue<ExNode> que;
58 ExNode start;
59 for(int i=0;i<n;i++)
60 start.num|=1<<i;
61 que.push(start);
62 while(!que.empty()){
63 ExNode f=que.top();
64 que.pop();
65 if(f.num==0){
66 printf("Fastest sequence takes %d seconds.\n\n",f.time);
67 return true;
68 }
69 ExNode d=f;
70 for(int i=0;i<m;i++){
71 d=f;
72 if(!((~d.num&vec[i].bplus)||(d.num&vec[i].bminus))){
73 d.num|=vec[i].eplus;
74 d.num&=(~vec[i].eminus);
75 d.time=f.time+vec[i].time;
76 if(hash[d.num]==-1||hash[d.num]>d.time){
77 hash[d.num]=d.time;
78 que.push(d);
79 }
80 }
81 }
82 }
83 return false;
84 }
85 int main()
86 {
87 int p=1;
88 while(scanf("%d%d",&n,&m),n+m){
89 Input();
90 printf("Product %d\n",p++);
91 if(BFS()==false){
92 printf("Bugs cannot be fixed.\n\n");
93 continue;
94 };
95 }
96 return 0;
97 }
posted on 2008-09-09 14:25
小果子 阅读(144)
评论(0) 编辑 收藏 引用