总结：
对于第一位的运算|运算，0|1取反，其他不变&运算，1&0取反，其他不变一定要把位运算的东西括起来再计算，如（1|0）+1,但不能是1|0+1。
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <queue> using namespace std; const int maxn=(1<<20)+100; int s[2][110],t[2][110]; int n,m; int w[110]; bool vis[maxn]; char a[50],b[50]; int dp[maxn]; const int inf=0x3f3f3f3f; void init() { memset(vis,0,sizeof(vis)); memset(s,0,sizeof(s)); memset(t,0,sizeof(t)); memset(dp,inf,sizeof(dp)); } void solved() { queue<int> q; int bug=(1<<n)-1; q.push(bug); dp[bug]=0; while(q.size()) { int u=q.front(); q.pop(); vis[u]=0;//防止之后有前面出现过的但权更小的串出现 for(int i=1; i<=m; i++) { if((u|s[1][i])==u&&(u&s[0][i])==u) { int v=u; v=v|t[1][i]; v=v&t[0][i]; if(dp[v]>dp[u]+w[i]) { dp[v]=dp[u]+w[i]; if(!vis[v])//同一层可以更新更小的dp，但相同的串就不用再放里面了 { q.push(v); vis[v]=1; } } } } } if(dp[0]<inf) printf("Fastest sequence takes %d seconds.\n",dp[0]); else printf("Bugs cannot be fixed.\n"); } int main() { int Case=0; while(~scanf("%d%d",&n,&m)&&(m+n)) { init(); for(int i=1; i<=m; i++) { scanf("%d%s%s",&w[i],a,b); for(int j=0; j<n; j++) { if(a[j]=='+') s[1][i]+=(1<<j); if(a[j]!='-') s[0][i]+=(1<<j); if(b[j]=='+') t[1][i]+=(1<<j); if(b[j]!='-') t[0][i]+=(1<<j); } } printf("Product %d\n",++Case); solved(); printf("\n"); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/8351129.html
相关资源：数据结构—成绩单生成器