本文共 1141 字，大约阅读时间需要 3 分钟。

题意： 用补丁修订bug，补丁修订bug时有一些要求，其中要求某些bug必须存在，某些bug必须不存在，有的bug任意，在打完补丁之后的状态 有的bug存在，有的消失，有的不变，每个补丁都有执行时间，任务是用最少的时间把一个所有bug都存在的软件通过打补丁的方式变得没有bug。一个补丁可以打多次。

有n（n≤20）个bug，m（≤100）个补丁。

思路：可以把软件拥有bug的状态当成节点，把打补丁的时间当作权值，题目就变成了有向图，题目就转换成求从节点（1<<n-1）到0的最短路径了。因为n小于等于20 这时可以用二进制表示每个bug的存在状态，转换成十进制就成了节点的值，节点的状态共有pow（2，20）种，状态太多，而且有些状态根本遇不到，所以我们不用把所有的状态都找，把图存起来，我们只需要遇到什么状态存什么状态就ok了。

在表示补丁修订bug时的状态，我们要注意保存方式，把必须存在的状态保存下来，不存在的状态保存下来。

#include 
   
    using namespace std;const int maxn=(1<<20)+50;const int inf=0x3f3f3f3f3f;int w[150],a[150][2],b[150][2];int dis[maxn];int vis[maxn];int n,m;void spfa(){    queue
    
      q;    memset(vis,0,sizeof(vis));    dis[(1<
     
      dis[u]+w[i])                {                    dis[v]=dis[u]+w[i];                    if(!vis[v])                    {                        q.push(v);                        vis[v]=1;                    }                }            }        }    }    if(dis[0]!=inf) cout<<"Fastest sequence takes "<
      
       <<" seconds."<
       
        >n>>m)    {        if(m+n==0) break;        ka++;        cout<<"Product "<
        
         <
         
          >w[i]>>s1>>s2; for(int j=0; j
         
        
       
      
     
    
   

转载地址：http://ufgsi.baihongyu.com/