记录编号	387165	评测结果	AAAAAAAA
题目名称	软件补丁	最终得分	100
用户昵称	nonamenotitle	是否通过	通过
代码语言	C++	运行时间	0.046 s
提交时间	2017-03-26 00:19:40	内存使用	10.32 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=21;
const int maxm=120;
int n,m;
struct point
{
	int f1,f2;//增加的错误 减少的错误
	int b1,b2;//需要的错误 不要的错误
	int cost;
}p[maxm];

int dis[1<<21];
bool inque[1<<21];

bool judge(int u,int i)
{
	bool flag=true;
	if((u|(p[i].b1))!=u)
	{
		/*
		printf("u|p[i].b1=%d\n",u|(p[i].b1));
		printf("%d\n",u);
		*/
		flag=false;
	}
	if(p[i].b2&u)//若p[i].b2&n不为0 
		//那么一定有一个数位上既是b2中不允许存在的
		//并且此数位在n中存在
	{
		flag=false;
	}
	return flag;
}

void spfa()
{
	queue<int > q;
	q.push((1<<n)-1);
	inque[(1<<(n))-1]=true;
	memset(dis,inf,sizeof(dis));
	dis[(1<<(n))-1]=0;
	while(!q.empty())
	{
		int now=q.front();
		q.pop();
		inque[now]=false;
		for(int i=0;i<m;i++)
		{
			if(judge(now,i))
			{
				int u=(now&(~p[i].f2))|(p[i].f1);
				/*
				printf("now=%d\n",now);
				printf("p[%d].f2=%d\n",i,p[i].f2);
				printf("~p[%d].f2=%d\n",i,~p[i].f2);
				printf("p[%d].f1=%d\n",i,p[i].f1);
				printf("%d\n",u);
				*/
				if(dis[u]>dis[now]+p[i].cost)
				{
					dis[u]=dis[now]+p[i].cost;
					if(!inque[u])
					{
						q.push(u);
						inque[u]=true;
					}
				}
			}
		}
	}
}

int main()
{
	freopen("bugs.in","r",stdin);
	freopen("bugs.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++)
	{
		int cost;
		char buff1[maxn],buff2[maxn];
		memset(buff1,0,sizeof(buff1));
		memset(buff2,0,sizeof(buff2));
		scanf("%d%s%s",&cost,buff1,buff2);
		p[i].cost=cost;
		int len=strlen(buff1);
		len--;
		for(int j=0;j<(int)strlen(buff1);j++)
		{
			if(buff1[j]=='+')
			{
				p[i].b1+=1<<(len-j);
			}
			if(buff1[j]=='-')
			{
				p[i].b2+=1<<(len-j);
			}
			if(buff2[j]=='+')
			{
				p[i].f1+=1<<(len-j);
			}
			if(buff2[j]=='-')
			{
				p[i].f2+=1<<(len-j);
			}
		}
	}
	spfa();
	/*
	printf("dis:\n");
	for(int i=0;i<1<<n;i++)
	{
		printf("%d ",dis[i]);
	}
	printf("\n");
	*/
	if(dis[0]!=inf)
	{
		printf("%d\n",dis[0]);
	}
	else
	{
		printf("-1\n");
	}
	return 0;
}