题目大意： 首先给出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不可能被完全消除那么就输出失败

solution: Dijkstra 或者 BellmanFord 求最短路。

ps：由于状态太多，所以不必提前建图，可以枚举每个状态，看是否匹配。

dijkstra

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 25;
const int M = 105;
#define Inf 0x3f3f3f3fint t[N], d[1<<20], vis[1<<20];
char U[M][N], V[M][N];
int n, m;struct HeapNode{int dist, bug;bool operator<(const HeapNode &rhs) const{return dist>rhs.dist;}
};int dijkstra(){priority_queue<HeapNode> Q;HeapNode start;start.dist=0;start.bug=(1<<n)-1;Q.push(start);for ( int i=0; i<=(1<<n)-1; i++ ) d[i]=Inf, vis[i]=0;   d[start.bug]=0;while( !Q.empty() ){HeapNode x=Q.top(); Q.pop();int u=x.bug;if( u==0 ) return x.dist;if( vis[u] ) continue;vis[u]=1;for ( int i=1; i<=m; i++ ){bool chk=true;for ( int j=0; j<n; j++ ){if ( U[i][j]=='-' && (u&(1<<j)) ) { chk=false; break; }if ( U[i][j]=='+' && !(u&(1<<j)) ) { chk=false; break;}  }if( !chk ) continue;HeapNode nxt;nxt.bug=x.bug;nxt.dist=x.dist+t[i];for ( int j=0; j<n; j++ ){if( V[i][j]=='-' ) nxt.bug&=~(1<<j);if( V[i][j]=='+' ) nxt.bug|=(1<<j);}if( d[nxt.bug]>nxt.dist ){d[nxt.bug]=nxt.dist;Q.push(nxt);}} }return -1;
} 
int main(){
// freopen("1.cpp","w",stdout);int k=0;while( ~scanf("%d%d", &n, &m ) && n ){for ( int i=1; i<=m; i++ ){scanf("%d%s%s", &t[i], U[i], V[i] );}int ans=dijkstra();printf("Product %d\n", ++k );if(ans < 0) printf("Bugs cannot be fixed.\n\n");    //需要注意题目要求的输出格式else printf("Fastest sequence takes %d seconds.\n\n", ans);}return 0;
}

BellmanFord

BellmanFord不能中途退出，因为这可能不是最短路。

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 25;
const int M = 105;
#define Inf 0x3f3f3f3fint t[N], d[1<<20], vis[1<<20];
char U[M][N], V[M][N];
int n, m;void Bellman_ford(){queue<int> Q;int sta=(1<<n)-1;for ( int i=0; i<=(1<<n)-1; i++ ) d[i]=Inf, vis[i]=0;d[sta]=0;Q.push(sta);while( !Q.empty() ){int u=Q.front(); Q.pop();vis[u]=0;for ( int i=1; i<=m; i++ ){bool chk=true;for ( int j=0; j<n; j++ ){if ( U[i][j]=='-' && (u&(1<<j)) ) { chk=false; break; }if ( U[i][j]=='+' && !(u&(1<<j)) ) { chk=false; break;}  }if( !chk ) continue;int v=u;for ( int j=0; j<n; j++ ) {if( V[i][j]=='-' ) v&=~(1<<j);if( V[i][j]=='+' ) v|=(1<<j);}if( d[v]>d[u]+t[i] ){d[v]=d[u]+t[i];if( !vis[v] ){vis[v]=1;Q.push(v);}}}}if(d[0] == Inf)  printf("Bugs cannot be fixed.\n");  else  printf("Fastest sequence takes %d seconds.\n",d[0]);  
}
int main(){int k=0;while( ~scanf("%d%d", &n, &m ) && n ){for ( int i=1; i<=m; i++ ){scanf("%d%s%s", &t[i], U[i], V[i] );}printf("Product %d\n", ++k );Bellman_ford();printf("\n");}return 0;
}