分析

裸的最短路：

把错误集合状压成一个二进制，第i为为1表示有第i个错误

把这个状态x作为图上的节点编号,dist[x]表示转移到状态x需要的时间

显然初始状态为dist[\(2^n-1\)]最终的答案为dist[0]

转移的时候枚举每一个补丁，通过位运算判断补丁i是否能修复当前状态

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define maxm 1005#define maxn 1<<21 #define INF 0x3f3f3f3fusing namespace std;int n,m;char s[maxm];int t[maxm];int b1[maxm],b2[maxm],f1[maxm],f2[maxm];int dist[maxn];int inq[maxn];int spfa(int s){    queue
         
          q; memset(dist,0x3f,sizeof(dist)); q.push(s); dist[s]=0; inq[s]=1; while(!q.empty()){ int x=q.front(); q.pop(); inq[x]=0; for(int i=1;i<=m;i++){//枚举每一个补丁 if((b1[i]|x)==x&&(b2[i]&x)==0){//x包括b1[i],不包括b2[i] int y=x^(x&f1[i]);//x&f1[i]为x中能被修复的错误,再异或就相当于把错误去掉 y|=f2[i];//加上新增的错误 if(dist[y]>dist[x]+t[i]){ dist[y]=dist[x]+t[i]; if(!inq[y]){ q.push(y); inq[y]=1; } } } } } if(dist[0]==INF) return 0; else return dist[0];}int main(){ scanf("%d %d",&n,&m); for(int i=1;i<=m;i++){ scanf("%d",&t[i]); scanf("%s",s); for(int j=0;j