记录编号	162182	评测结果	AAAAAAAA
题目名称	439.软件补丁	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2015-05-14 20:05:57	内存使用	16.32 MiB

#include<cstdio>
#include<deque> 
#include<string>
#include<iostream>
using namespace std;
const int maxm=(1<<21)+50,maxn=0x7fffffff;
int n,sw[maxm]={0},m,now;
class miku
{
public:
	int w;
	string fr,to;
};
deque<int> Q;
int iq[maxm]={0};
miku s[110];
int spfa()
{
	iq[now]=1;
	Q.push_back(now);
	for(int i=0;i<now;i++)
		sw[i]=maxn;
	sw[now]=0;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop_front();
		int tem,temp,temp2;
		iq[x]=0;
		for(int i=1;i<=m;i++)
		{
			tem=x;temp=0;temp2=0;
			for(int j=n-1;j>=0;j--)
			{
				if((s[i].fr[j]=='-'&&(tem&1)==1)||(s[i].fr[j]=='+'&&(tem&1)==0))
				{
					goto NEXT;
				}
				else
				{
					//cout<<x<<" "<<tem<<" "<<s[i].to<<endl;
					temp2<<=1;
					if(s[i].to[j]=='+')
						temp2+=1;
					if(s[i].to[j]=='0')
					{
						temp2+=(tem&1);
					}
					tem>>=1;
				}
			}
			//cout<<temp2<<endl;
			for(int j=1;j<=n;j++)
			{
				temp<<=1;
				temp+=temp2%2;
				temp2>>=1;
			}
			//cout<<temp<<endl;
			if(sw[x]+s[i].w<sw[temp])
			{
				sw[temp]=sw[x]+s[i].w;
				//cout<<x<<" "<<s[i].w<<" "<<s[i].fr<<" "<<s[i].to<<" "<<temp<<" "<<sw[temp]<<" "<<iq[temp]<<endl;
				if(iq[temp]==0)
				{
					iq[temp]=1;
					Q.push_back(temp);
				}
			}
			NEXT:;
		}
	}
	return 0;
}
int main()
{
	freopen("bugs.in","r",stdin);
	freopen("bugs.out","w",stdout);
	scanf("%d%d",&n,&m);
	now=(1<<(n))-1;
	for(int i=1;i<=m;i++)
	{
		cin>>s[i].w>>s[i].fr>>s[i].to;
	}
	//cout<<now<<" "<<n<<" "<<m<<endl;
	spfa();
	if(sw[0]!=maxn)
	printf("%d",sw[0]);
	else
	{
		printf("-1");
	}
	return 0;
}