poj1482（隐式图求最短路） - c++编程基础

题目链接

题意：补丁在修正bug时，有时也会引入新的bug。假定有n个潜在的bug m个补丁，每个补丁用两个长度为n的字符串表示，其中字符串的每个位置表示一个bug，第一个串表示打补丁之前的状态('-'表示该bug必须不存在，’+‘表示必须存在，0表示无所谓，第二个串表示打补丁之后的状态(-'表示不存在，’+‘表示存在，0表示不变)。每个补丁都有一个执行时间，你的任务使用最少的时间把一个bug都存在的软件通过打补丁的方式变得没有bug。一个补丁可以打多次。

解法：状压表示每个补丁的存在与否。隐式搜索，会有很多状态根本搜不到，spfa直接搜索即可。对于每次都枚举使用所有的补丁修补并松弛得到的状态。

代码：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=10100000; const LL INF=0x3FFFFFFF; int state[(1<<20)+10]; int n,m; struct bug { int cost; char start[22]; char end[22]; } bugs[1200]; bool operator<(const bug& a,const bug& b) { return a.cost
              
               >n>>m) { if(n==0&&m==0) break; for(int i=0; i
               
                state[t]+bugs[i].cost)) { state[st]=state[t]+bugs[i].cost; if(!rem[st]) que[right++]=st,rem[st]=1; } } rem[t]=0; } printf("Product %d\n",kk++); if(state[0]==-1) puts("Bugs cannot be fixed."); else { printf("Fastest sequence takes %d seconds.\n",state[0]); } cout<