记录编号	285174	评测结果	AAAAAAAA
题目名称	软件补丁	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2016-07-21 09:19:13	内存使用	0.34 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
const int maxn=110;
const int INF=1000000000;
map<int,bool>vis;
map<int,int>dis;
int n,m,val[maxn];
char op[maxn][maxn];
char tp[maxn][maxn];
queue<int>q;
int main(){
	freopen("bugs.in","r",stdin);
	freopen("bugs.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&val[i]);
		scanf("%s",op[i]+1);
		scanf("%s",tp[i]+1);
	}
	
	q.push(0);vis[0]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();vis[x]=0;
		for(int t=1;t<=m;t++){
			int f=1;
			for(int i=1;i<=n;i++)
				if(!(x>>i-1&1)&&op[t][i]=='-'||x>>i-1&1&&op[t][i]=='+'){f=0;break;}
					
			if(f==0)continue;
			int y=x;
			for(int i=1;i<=n;i++){
				if(tp[t][i]=='+')y&=((1<<n)-1)^(1<<(i-1));
				if(tp[t][i]=='-')y|=1<<(i-1);
			}	
			if(dis[y]==0&&y)dis[y]=INF;
			if(dis[x]+val[t]<dis[y]){
				dis[y]=dis[x]+val[t];
				if(!vis[y]){
					q.push(y);
					vis[y]=1;
				}
			}
		}
	}
	if(dis[(1<<n)-1]!=0)
		printf("%d\n",dis[(1<<n)-1]);
	else printf("-1\n");	
	return 0;
}