题意：有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 #include2 #include 3 #include 4 #include 5 #include 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 node14 {15 int bug,d;16 node() {}17 node(int u,int v) {bug=u;d=v;}18 bool operator < (const node& now) const19 { return d>now.d; }//return!!!20 };21 priority_queue q;22 23 bool check(int x,int k)24 {25 for (int i=0;i
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include