记录编号	356957	评测结果	AAAAAAAA
题目名称	软件补丁	最终得分	100
用户昵称	Rapiz	是否通过	通过
代码语言	C++	运行时间	0.036 s
提交时间	2016-12-07 20:12:05	内存使用	5.32 MiB

#include <cstdio>
#include <queue>
#include <cstring>
#define file(x) "bugs." #x
const int V = (1 << 20) + 10, M = 110, N = 25, INF = 0x3f3f3f3f;
int d[V], n, m, w[M];
bool inq[V];
char p[M][2][N];
inline void set(int& o, int x, int v) {
	if (v) o = o | (1 << x);
	else o = o & ~(1 << x);
}
bool fix(int o, int& t, char p[2][N]) {
	t = 0;
	for (int i = 0, x = o; i < n; i++, x >>= 1) {
		if (p[0][i] != '0') {
			if (p[0][i] == '+' && !(x&1)) return 0;
			if (p[0][i] == '-' && x&1) return 0;
		}
		if (p[1][i] == '0') set(t, i, x&1);
		else if (p[1][i] == '+') set(t, i, 1);
		else if (p[1][i] == '-') set(t, i, 0);
	} 
	return 1;
}
void show(int x) {
	for (int i = 1; i <= n; i++, x >>= 1) putchar((x&1) + '0');
}
std::queue<int> q;
int main() {
	freopen(file(in), "r", stdin);
	freopen(file(out), "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%s%s", &w[i], p[i][0], p[i][1]);
	}
#ifdef TEST
	int x;
	show(x = (1 << n) - 1);
	fix(x, x, p[1]);
	show(x);
	printf("%d\n", fix(x, x, p[2]));
	show(x);
	return 0;
#endif
	memset(d, 0x3f, sizeof(d));
	d[(1 << n) - 1] = 0;
	inq[(1 << n) - 1] = 1;
	q.push((1 << n) - 1);
	while (!q.empty()) {
		int u = q.front();q.pop();
		inq[u] = 0;
		for (int i = 1, v; i <= m; i++) if (fix(u, v, p[i]) && d[v] > d[u] + w[i]) {
			d[v] = d[u] + w[i];
			if (!inq[v]) inq[v] = 1, q.push(v);
		}
	}
	printf("%d", d[0] == INF ? -1 : d[0]);
}