记录编号	16197	评测结果	AAAAAAAA
题目名称	软件补丁	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2010-04-22 11:52:02	内存使用	24.26 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>

using namespace std;

const int oo=2000000000;

int d[1<<21];
char beg[101][21],en[101][21];
int cost [101],n,m;
void init()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d",&cost[i]);
		scanf("%s",beg[i]);
		scanf("%s",en[i]);
	}
}

struct HH
{
	int h;
	int id[1<<21],weizhi[1<<21];
	
	inline void sswap(int i,int j)
	{
		int t;
		t=id[i];
		id[i]=id[j];
		id[j]=t;
		t=weizhi[id[i]];
		weizhi[id[i]]=weizhi[id[j]];
		weizhi[id[j]]=t;
	}
	
	void push(int idd)
	{
		h++;
		id[h]=idd;
		weizhi[idd]=h;
		int now=h;
		while (now!=1 && d[id[now]]<d[id[now/2]])
		{
			sswap(now,now/2);
			now=now/2;
		}
	}
	
	int pop()
	{
		int po=id[1];
		weizhi[po]=0;
		id[1]=id[h];
		weizhi[id[h]]=1;
		h--;
		int now=1;
		while (now*2<=h && (d[id[now]]>d[id[now*2]] || d[id[now]]>d[id[now*2+1]]))
		{
			if (now*2==h)
			{
				if (d[id[now]]>d[id[now*2]]) 
				{	
					sswap(now,now*2);
					now=now*2;
				}
				else break;
			}
			else
			{
				int t;
				if (d[id[now*2+1]]>d[id[now*2]]) t=now*2;
				else t=now*2+1;
				sswap(now,t);
				now=t;
			}
		}
		return po;
	}
	
	void tisheng(int i)
	{
		int now=weizhi[i];
		while (now!=1 && d[id[now]]<d[id[now/2]])
		{
			sswap(now,now/2);
			now=now/2;
		}
	}
}heap;

int djs()
{
	for (int i=1;i<(1<<n);i++) d[i]=oo;
	heap.push(0);
	
	while (heap.h>0)
	{
		int u=heap.pop();
		if (u==(1<<n)-1) return d[u];
		for (int i=1;i<=m;i++)
		{
			int j;
			for (j=0;j<n;j++)
			{
				if (beg[i][j]=='+' && (u>>j & 1)) break;
				else if (beg[i][j]=='-' && !(u>>j & 1)) break;
			}
			if (j>=n)
			{
				int v=u;
				for (j=0;j<n;j++)
				{
					if (en[i][j]=='+' && (u>>j & 1)) v-= 1<<j;
					else if (en[i][j]=='-' && !(u>>j & 1)) v+= 1<<j;
				}
				if (d[v]>d[u]+cost[i])
				{
					d[v]=d[u]+cost[i];
					if (!heap.weizhi[v]) heap.push(v);
					else heap.tisheng(v);
				}
			}
		}
	}
	return -1;
}


int main()
{
	freopen("bugs.in","r",stdin);
	freopen("bugs.out","w",stdout);
	init();
	cout<<djs()<<endl;
	return 0;
}