题目大意：
假定有n个潜在的bug和m个补丁，每个补丁用长为n的字符串表示。首先输入bug数目以及补丁数目。然后就是对m 个补丁的描述，共有m行。每行首先是一个整数，表明打该补丁所需要的时间。然后是两个字符串，地一个字符串 是对软件的描述，只有软件处于该状态下才能打该补丁该字符串的每一个位置代表bug状态（-代表该位置没bug,+代 表该位置有bug，0表示该位置无论有没有bug都可打补丁）。然后第二个字符串是对打上补丁后软件状态的描述 -代表该位置上的bug已经被修复，+表示该位置又引入了一个新的bug, 0表示该位置跟原来状态一样）。要求用最少 时间完成对软件的修复，即将所有位置全都置为0.
基本思路：
状态压缩一下转化为最短路来处理
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const int maxn = 1000000000+10;
int n,m,t[110],d[1<<20],vis[1<<20];
char before[110][25],after[110][25];
struct Node{
int bug,dist;
bool operator<(const Node& rhs)const{
return dist>rhs.dist;
}
};
int dijkstra(){
for(int i=0;i<(1<<n);i++){
d[i]=inf;
vis[i]=0;
}
priority_queue<Node>q;
Node start;
start.bug=(1<<n)-1;
start.dist=0;
q.push(start);
d[start.bug]=0;
while(!q.empty()){
Node x=q.top();q.pop();
if(x.bug==0) return x.dist;
if(vis[x.bug]) continue;
vis[x.bug]=1;
for(int i=0;i<m;i++){
bool pat=true;
for(int j=0;j<n;j++){
if(before[i][j]=='-'&&(x.bug&(1<<j))){
pat=false;
break;
}
if(before[i][j]=='+'&&!(x.bug&(1<<j))){
pat=false;
break;
}
}
if(!pat) continue;
Node next;
next.bug=x.bug;
next.dist=x.dist+t[i];
for(int j=0;j<n;j++){
if(after[i][j]=='-') next.bug&=~(1<<j);
if(after[i][j]=='+') next.bug|=(1<<j);
}
int &D=d[next.bug];
if(next.dist<D){
D=next.dist;
q.push(next);
}
}
}
return -1;
}
int main(){
int cas=0;
while(scanf("%d%d",&n,&m)==2&&n){
for(int i=0;i<m;i++){
scanf("%d%s%s",&t[i],&before[i],&after[i]);
}
int ans=dijkstra();
printf("Product %d
",++cas);
if(ans<0){
printf("Bugs cannot be fixed.
");
}else{
printf("Fastest sequence takes %d seconds.
",ans);
}
}
return 0;
}