记录编号	236745	评测结果	AAAAAAAA
题目名称	软件补丁	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-03-15 14:05:52	内存使用	24.16 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue> 
using namespace std;
const int maxn = 1e6;
const int inf = 2139062143;
int dis[5*maxn];
bool inque[5*maxn];
int bit[25];
int n, m;
//每一位上0表示已经修复，1表示没有修复 
struct node {
	int v;
	int fr, make, fix;
	int none_fr;
	//none存储0 
	//修复了可以不用管，用0，产生了用1 
}ns[105];
inline void get_bit_var() {
	for(int i = 1; i <= 20; i++) {
		bit[i] = 1<<(i-1);
	}
}
inline int solve() {
	queue<int> q;
	q.push((1<<n)-1);
	dis[(1<<n)-1] = 0;
	int now, tmp, to;
	while(!q.empty()) {
		now = q.front(); q.pop();
		for(int i = 1; i <= m; i++) {
			tmp = (now | ns[i].none_fr);
			if(tmp == ns[i].fr) {
				tmp = (now | ns[i].make);
				to = tmp - (tmp & ns[i].fix);
				if(!dis[to] || dis[to] >= dis[now]+ns[i].v) {
					dis[to] = dis[now]+ns[i].v;
					if(!inque[to]) {
						q.push(to);
						inque[to] = true;
					}
				}
			}
		}
		inque[now] = false;
	}
	return dis[0] == 0 ? -1 : dis[0];
}
inline void read() {
	scanf("%d %d", &n, &m);
	char s1[25], s2[25];
	int v;
	for(int i = 1; i <= m; i++) {
		scanf("%d %s %s", &v, s1+1, s2+1);
		ns[i].v = v;
		for(int j = 1; j <= n; j++) {
			if(s1[j] == '+') {
				ns[i].fr += bit[n-j+1];//要求存在 i  
			} else if(s1[j] == '0') {
				ns[i].none_fr += bit[n-j+1];//无所谓 
				ns[i].fr += bit[n-j+1];
			}
			if(s2[j] == '+') {//产生i，剩 
				ns[i].make += bit[n-j+1];
			} else if(s2[j] == '-') {
				ns[i].fix += bit[n-j+1];
			}
		}
	}
} 
int main() {
	freopen("bugs.in", "r", stdin);
	freopen("bugs.out", "w", stdout);
	get_bit_var();
	read();
	printf("%d",solve());
	return 0;
}