最短路（隐式图搜索）

题目是过了，不过时间好慢，用了2.200s。大概是没有用位运算的原因，我是直接模拟的。而解决最短路的问题是用spfa来做（感觉这种思路更加形象和容易理解，并且更符合隐式图搜索的感觉）

来说说题意，这个题意都是很长很烦的。首先给出n和m，表示有n个bug和m个补丁。一开始存在n个bug，用1表示一个bug存在0表示不存在，所以一开始就是n个1，我们的目的是要消除所有的bug，所以目标状态就是n个0。对于每个补丁，会给出使用这个补丁的时间，另外会给出两个长度为n的字符串，第一个字符串表示这个补丁适用于什么情况下的bug，第二个字符串表示使用完这个补丁后原来的bug会变成怎么样。先说第一个字符串，s[i]='0'，表示第i个bug存在与否都无所谓；s[i]='+'，表示第i个bug一定要存在；s[i]='-'，表示第i个bug必须不存在；能不能使用这个补丁，就要看当前bug的状态是不是能不能全部满足第一个字符串，能的话就可以使用。第二个字符串表示使用完后的情况，ss[i]='0'，表示第i个bug保持不变，原来是1就1是0就0；ss[i]='+'，表示第i个bug必须为1；ss[i]='-'，表示第i个bug必须为0。

最终题目要求解的就是消除所有的bug并且用时最短，输出最短时间，如果bug不可能被完全消除那么就输出失败

 

这个题目可以转化为最短路的模型来求解。由n个1或0来表示bug，我们很容易联想要二进制和十进制的转化，对于当前的bug状态，我们可以转化为1个十进制来表示，那么一开始的状态显然就是2^n-1，目标状态就是0，也就是从2^n-1转化为0，用时最少，相当于从2^n-1到0的最短路

对于一个补丁，其实就是一些有向边（是有向边，而且不是一条，可能是多条，所以是一些），为什么？因为对于当前的bug状态我们转化为十进制u，扫描所有的补丁，找到可以使用的补丁，并在这个补丁作用下变为一个新的bug状态，这个新的bug状态也对应一个十进制v，所以其实就是u到v，有向边u-->v，边权就是使用补丁使用的时间。

一种思路是先建图，再来一个最短路，但是会超时，因为图的顶点太多，边也很多。n的上限是20，即顶点个数为2^20-1，而边数在最坏情况下很大的，一定会超时。而我们思考可以知道，很多顶点是不一定会经过的，也就是很多bug的状态不会出现，所以我们为什么不一边最短路一边建图呢？所以就用spfa来做。而这题边权是不会为负的，所以也可以用dij

 

这题只要处理好细节，AC是没问题，但是想时间快点，就要用一些技巧。主要区别在于，怎么判断哪些补丁适用于当前的bug，另外使用后怎么快速得到新的bug状态等等，这些都可以用位运算来提高速度。

另外就是如果用dij的优先队列应该会比spfa更快。

 

另外注意一个问题，不知道是我自己的代码的问题还是本质上的错误。就是关系bug二进制的保存。好像10000，表示16，一开始我为了方便运算是逆过来保存00001，然后去计算新的状态也是逆过来保存，然后就一直TLE。后来我改回来顺着保存，就AC了。

 

代码有点长…………

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define INF 0x3f3f3f3f#define N 25#define M 110#define MAX 1048600int n,m,s,t;int d[MAX],vis[MAX],a[N];int bug[N],newbug[N];struct patches{    char b0[N],b[N];    int t;};typedef struct patches patches;patches p[M];void get_bug(int x){    //memset(bug,0,sizeof(bug));    for(int i=n-1; i>=0; i--)    {        bug[i]=x%2;        x/=2;    }/*    printf("get_bug\n");    for(int i=0; i
        
         =0; i--)    {        if(p[k].b[i]=='0')            newbug[i]=bug[i];        else if(p[k].b[i]=='+')            newbug[i]=1;        else            newbug[i]=0;    }    int val=0;    for(int i=n-1,j=0; i>=0; i--,j++)        val+=newbug[i]*a[j];/*    printf("get_newbug\n");    for(int i=0; i
         

q; s=0; t=0; for(int i=0; i