记录编号	572319	评测结果	AAAAAAAA
题目名称	软件补丁	最终得分	100
用户昵称	HeSn	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2022-06-30 16:46:28	内存使用	19.31 MiB

#include<bits/stdc++.h> 
using namespace std;
const int N=1<<22, M=105, INF=0x3f3f3f3f;
struct pack {
	int b1, b2, f1, f2, t;
}p[M];
int n, m, d[N];
bool v[N];
char ch, s[22];
bool SPFA() {
	memset(d, 0x3f, sizeof(d));
	queue<int> q;
	int x = (1 << n) - 1;
	d[x] = 0;
	q.push(x);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		v[u] = 0;
		for(int i = 1; i <= m; i ++) {
			if((u & p[i].b1) == p[i].b1 && (u & p[i].b2) == 0) {
				int nxt = ((u | p[i].f1) ^ p[i].f1) | p[i].f2;
				if(d[nxt] > d[u] + p[i].t) {
					d[nxt] = d[u] + p[i].t;
					if(v[nxt] == 0) {
						v[nxt] = 1;
						q.push(nxt);
					}
				}
			}
		}
	}
	return d[0] != INF;
}
int main() {
	freopen("bugs.in", "r", stdin);
	freopen("bugs.out", "w", stdout);
	cin >> n >> m;
	char s1[22], s2[22];
	for(int i = 1; i <= m; i ++) {
		cin >> p[i].t;
		scanf("%s%s", s1, s2);
		for(int j = 0; j < n; j ++) {
			if(s1[j] == '+') {
				p[i].b1 |= 1 << j;
			}
			else if(s1[j]=='-') {
				p[i].b2 |= 1 << j;
			}
		}
		for(int j = 0; j < n; j ++) {
			if(s2[j] == '+') {
				p[i].f2 |= 1 << j;
			}
			else if(s2[j]=='-') {
				p[i].f1 |= 1 << j;
			}
		}
	}
	if(SPFA()) {
		cout << d[0] << endl;
	}
	else {
		cout << -1 << endl;
	}
	return 0;	
}