UVA658 这不是bug，而是特性 It's not a Bug, it's a Feature! 题解

#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
	x=0;char ch;
	bool f=false;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar())
		if (ch=='-')
			f=true;
	for(;ch>='0'&&ch<='9';ch=getchar())
		x=(x<<3)+(x<<1)+(ch&15);
	if (f) x=-x;
}
inline void wr(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) wr(x/10);
	putchar(x%10+'0');
	return;
}//快读写
const int N=1<<20;
int n,m,s,a[N],b[N],c[N],d[N],l;
long long dis[N],t[N];
set<pair<long,int> >q;
void Dijkstra(){
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	q.insert({0,s});
	while(!q.empty()){
		int x=q.begin()->second;
		q.erase(q.begin());
		for(int i=1;i<=m;i++){
			if(((x&a[i])==a[i])&(x&b[i])==0){
				int y=(x|c[i])&d[i];
				if(dis[y]>dis[x]+t[i]){
					dis[y]=dis[x]+t[i];
					q.insert({dis[y],y});
				}
			}
		}
	}
}
int main(){
	while(1){
		rd(n),rd(m);
		if(n==0&&m==0)break;
		s=(1<<n)-1;
		for(int i=1;i<=m;i++){
			string c1,c2;
			cin>>t[i]>>c1>>c2;
			a[i]=0;b[i]=0;c[i]=0;
		for(int j=0;j<n;j++){
				if(c1[j]=='+')a[i]|=(1<<j);
				else if(c1[j]=='-')b[i]|=(1<<j);
				d[i]=s;
			}
			for(int j=0;j<n;j++){
				if(c2[j]=='+')c[i]|=(1<<j);
				else if(c2[j]=='-')d[i]^=(1<<j);
			}
		}//二进制
		Dijkstra();
		cout<<"Product "<<++l<<endl;
		if(dis[0]==0x3f3f3f3f3f3f3f3f)cout<<"Bugs cannot be fixed."<<endl;
		else cout<<"Fastest sequence takes "<<dis[0]<<" seconds."<<endl;
		cout<<endl;
	}
	return 0;
}