题意：有N个潜在的bug和m个补丁，每个补丁用长为N的字符串表示。首先输入bug数目以及补丁数目。然后就是对M个补丁的描述，共有M行。每行首先是一个整数，表明打该补丁所需要的时间。然后是两个字符串，第一个字符串是对软件的描述，只有软件处于该状态下才能打该补丁该字符串的每一个位置代表bug状态（"-"代表该位置没bug,"+"代表该位置有bug，"0"表示该位置无论有没有bug都可打补丁）。然后第二个字符串是对打上补丁后软件状态的描述"-"代表该位置上的bug已经被修复，"+"表示该位置又引入了一个新的bug, "0"表示该位置跟原来状态一样）。要求用最少时间完成对软件的修复，即将所有位置全都置为0。(N≤20)
解法：对每个bug用二进制表示，补丁两端的点通过边来转换，共2^n-1个结点。由于这样的点太多了，而实际上我们不需要这么多点。于是便像“隐式图搜索”一样，不知道所有的点，便通过所有的边来拓展。在这题中，也就是不是像平常一样用邻接表来拓展，而是枚举所有补丁，看是否能用上这条边。（注意"0"既可表示"+"，也可表示"-"）这样就可以从源点“11...11”开始用Dijkstra边求解边建图，直到"00...00"。
注意——由于用到了二进制的位运算，该加括号的地方千万不要漏；Dijkstra中优先队列的top()是汇点的值时就可以跳出，因为剩下的可以拓展的点都比它的值大，由于没有负权边，就不可能通过一些边又比它小了。
另外，本来我想偷懒不分析时间复杂度的，但是！！（o´・ェ・｀o）我发现Dijkstra+优先队列的算法的时间是spfa的好几倍啊！于是我还是分析了一下......
Dijkstra+优先队列：由于是类“隐式图搜索”，所以每个点进行拓展的操作都是m。原先的时间复杂度是O(n log n+m)，其中加的m就是每个点拓展时总共访问过一次的边。而此时这里要+km，k表示在汇点出队前入队的点树，因为每个点拓展时都遍历了一次m条所有的边啊。因此总的是O(n log n+km)，最坏情况O(n log n+nm)，而最坏的点是2^n。o(─.─|||
spfa:原来的时间复杂度是O(km)，k为每个节点进入队列的次数，且k一般<=2。而这里尽管每个点拓展时遍历了所有边，但依旧没有使它的复杂度改变多少!!!∑(ﾟДﾟノ)ノ 因为它本来主要承担这个时间复杂度的就是这个"km"啊！
总的来说就是——类“隐式图搜索”还是用spfa吧。
你们可以看看代码感受一下~ ╮(╯_╰)╭ P.S.我打得真的好粗心，所以注释有一点点儿多啊~
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 #include<queue>
6 using namespace std;
7
8 const int N=25,NN=1<<20,M=105,INF=(int)2e9;
9 int n,m;
10 int d[NN],vis[NN];
11 struct patch{int d;char s[N],ss[N];}a[M];
12
13 struct node
14 {
15 int bug,d;
16 node() {}
17 node(int u,int v) {bug=u;d=v;}
18 bool operator < (const node& now) const
19 { return d>now.d; }//return!!!
20 };
21 priority_queue<node> q;
22
23 bool check(int x,int k)
24 {
25 for (int i=0;i<n;i++)
26 {
27 int tmp=1<<i;//反着看二进制也没什么不行的（110表示一般的011），只要没有搞错位数就好了
28 if (a[k].s[i]=='+'&& !(x&tmp)) return false;
29 if (a[k].s[i]=='-'&& (x&tmp)) return false;//()
30 }
31 return true;
32 }
33 int trans(int x,int k)
34 {
35 int full=(1<<n)-1;//()
36 for (int i=0;i<n;i++)
37 {
38 int tmp=1<<i;
39 if (a[k].ss[i]=='+') x|=tmp;
40 if (a[k].ss[i]=='-') x&=(full-tmp);//&(full-tmp) 或 & ~tmp
41 }
42 return x;
43 }
44 int solve()
45 {
46 int tmp=(1<<n)-1;//node:0~tmp
47 while (!q.empty()) q.pop();
48 for (int i=0;i<=tmp;i++) d[i]=INF,vis[i]=0;
49 node st=node(tmp,0);
50 q.push(st); d[tmp]=0;
51 while (!q.empty())
52 {
53 int x=q.top().bug;
54 if (!x) return d[0];//notice，别的再更新也是从大于它的d[x]开始更新，无更优的解了
55 q.pop();
56 if (vis[x]) continue;
57 vis[x]=1;
58 for (int i=1;i<=m;i++)
59 {
60 if (!check(x,i)) continue;
61 int y=trans(x,i);
62 if (d[x]+a[i].d<d[y])
63 {
64 d[y]=d[x]+a[i].d;
65 q.push(node(y,d[y]));
66 }
67 }
68 }
69 if (d[0]!=INF) return d[0];
70 return -1;
71 }
72 int main()
73 {
74 int T=0;
75 while (1)
76 {
77 scanf("%d%d",&n,&m);
78 if (!n && !m) break;
79 for (int i=1;i<=m;i++)
80 scanf("%d%s%s",&a[i].d,a[i].s,a[i].ss);
81 int ans=solve();
82 printf("Product %d\n",++T);
83 if (ans==-1) printf("Bugs cannot be fixed.\n");
84 else printf("Fastest sequence takes %d seconds.\n",ans);
85 printf("\n");
86 }
87 return 0;
88 }
Dijkstra+优先队列
1 #include <cstdio>
2 #include <queue>
3 #include <cstring>
4 #include <iostream>
5 #include <cstdlib>
6 #include <algorithm>
7 #include <vector>
8 #include <map>
9 #include <string>
10 #include <set>
11 #include <ctime>
12 #include <cmath>
13 #include <cctype>
14 using namespace std;
15 #define MAX 100000
16 const int maxn = 110;
17 const int INF = 0x3f3f3f3f;
18 #define LL long long
19 int vis[(1<<20)+10];
20 int d[(1<<20)+10];
21 int s[2][maxn];
22 int t[2][maxn];
23 string s1,s2;
24 int n,m,w[maxn];
25 void dij()
26 {
27 int Max=(1<<n)-1;
28 queue<int>q;
29 for (int i = 0;i<Max;i++)
30 {
31 vis[i]=0;
32 d[i]=INF;
33 }
34 d[Max]=0;
35 q.push(Max);
36 int u,v;
37 while (!q.empty())
38 {
39 u=q.front();
40 vis[u]=0;
41 q.pop();
42 for (int i = 0;i<m;i++)
43 {
44 if ((u | s[1][i])== u && (u & (s[0][i]))==u)
45 {
46 v=u;
47 v = v | t[1][i];
48 v = v & t[0][i];
49 if (d[u]+w[i] <d[v])
50 {
51 d[v]=d[u]+w[i];
52 if (!vis[v])
53 {
54 q.push(v);
55 vis[v]=1;
56 }
57 }
58 }
59 }
60 }
61 if (d[0]==INF)
62 printf("Bugs cannot be fixed.\n");
63 else
64 printf("Fastest sequence takes %d seconds.\n",d[0]);
65 }
66 int cas=1,T;
67
68 int main()
69 {
70 while (scanf("%d%d",&n,&m)!=EOF && n)
71 {
72 memset(s,0,sizeof(s));
73 memset(t,0,sizeof(t));
74 for (int i = 0;i<m;i++)
75 {
76 cin >> w[i] >> s1 >> s2;
77 for (int j = 0;j<n;j++)
78 {
79 if (s1[j]=='+')
80 s[1][i]+=(1<<j);
81 if (s1[j]!='-')
82 s[0][i]+=(1<<j);
83 if (s2[j]=='+')
84 t[1][i]+=(1<<j);
85 if (s2[j]!='-')
86 t[0][i]+=(1<<j);
87 }
88 }
89 printf("Product %d\n",cas++);
90 dij();
91 printf("\n");
92 }
93 return 0;
94 }
spfa(来源于网上)