Patches

Problem description

A program always has an error , Companies often release patches to fix these errors , Unfortunately , Every patch used , When fixing some mistakes , At the same time, some errors will be added , Each patch has a certain running time .
A company published a game , There is n A mistake B={b1,b2,b3,…,bn}, So the company released m A patch , The application of each patch is conditional （ That is, which errors must exist , Which errors cannot exist ）.
Find out how much time it will take to correct all these errors .

Input

The first line of the input file has two positive integers n and m,n Represents the total number of errors ,m Represents the total number of patches ,1≤n≤20, 1≤m≤100. Next m Line gives m Information about a patch . Each line contains a positive integer （ Indicates the running time of this patch ） And two strings ,
The first string describes the conditions for applying the patch . String number i Characters , If it is ‘+’, Indicates that there must be no.. In the software bi Wrong number ; If it is ‘-’, Indicates an error in the software bi Can't exist ; If it is ‘0’, Indicates an error bi Exist or not exist （ That is, it has no effect on the application of this patch ）.
The second string describes the effect of applying the patch . String number i individual , If it is ‘+’, Indicates that a new error has occurred bi; If it is ‘-’, Indicates an error bi It's been revised ; If it is ‘0’, Indicates an error bi unchanged （ That is, the original , There is still ; It didn't exist , There is still no ）.

Output

Output an integer , If there is a problem , Total output time . Otherwise output -1.

Sample Input

3 5
1 0-+ -+-
3 +-- -00
4 000 00-
6 +0+ -0-
3 0+0 0-0

Sample Output

7

The main idea of the topic

At first there were many bug, We put bug Marked as ＋
So the beginning is +++, Our goal is —
Each patch must meet the conditions before it can be used , But the patch will also cause new bug. Then your task is to find an optimal solution to fix all bug.

Thinking analysis

This question is mainly two knowledge points , One is state compression , The other is spfa The use of algorithms .
here spfa It can also be used. Dijkstra Heap optimization method to complete the construction .
Because the graph here is that each point may form , It may not constitute penetration .
So we have to run all nodes violently for every exit , See if you can connect and use spfa Run straight
State compression is the node of each character 0 or 1. We can drive int Be able to store 32 A guarantee is enough .
Next is the operation of bit operation .
Here we need to pay attention to , He has a total of 2²⁰ possibility

Accepted Code

//#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<string.h>
#include <iomanip>
#include<stdio.h>
#include<vector>
#include<string>
#include<math.h>
#include<cmath>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll ll_inf = 9223372036854775807;
const int int_inf = 2147483647;
const short short_inf = 32767;
const ll less_inf = 0x3f3f3f3f;
const char char_inf = 127;
#pragma GCC optimize(2)
#define accelerate cin.tie(NULL);cout.tie(NULL);ios::sync_with_stdio(false);
#define PI 3.141592653589793
#define EPS 1.0e-8
ll gcd(ll a, ll b) {
    
	return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    
	return a / gcd(a, b) * b;
}
inline ll read() {
    
	ll c = getchar(), Nig = 1, x = 0;
	while (!isdigit(c) && c != '-')c = getchar();
	if (c == '-')Nig = -1, c = getchar();
	while (isdigit(c))x = ((x << 1) + (x << 3)) + (c ^ '0'), c = getchar();
	return Nig * x;
}
inline void out(ll a) {
    
	if (a < 0)putchar('-'), a = -a;
	if (a > 9)out(a / 10);
	putchar(a % 10 + '0');
}
ll qpow(ll x, ll n, ll mod) {
    
	ll res = 1;
	while (n > 0) {
    
		if (n & 1)res = (res * x) % mod;
		x = (x * x) % mod;
		n >>= 1;
	}
	return res;
}
#define read read()
const int MAXN = 4000000, N = 105;
int n, m;
bool judge[MAXN];
int dis[MAXN];
int A[N], B[N], C[N], D[N], val[N];
queue<int>q;
void spfa(ll sta) {
    
	memset(dis, 0x3f3f3f3f, sizeof(dis));
	dis[sta] = 0;
	q.push(sta);
	while (q.size()) {
    
		int x = q.front(), y;
		q.pop();
		judge[x] = false;
		for (int i = 0; i < m; i++) {
    
			if ((A[i] & x) == A[i] && (B[i] & x) == 0) {
    
				y = ((x | C[i]) ^ C[i]) | D[i];
				if (dis[x] + val[i] < dis[y]) {
    
					dis[y] = dis[x] + val[i];
					if (!judge[y])judge[y] = true, q.push(y);
				}
			}
		}
	}
}
int main()
{
    
	n = read, m = read;
	char a[50], b[50];
	for (int i = 0; i < m; i++) {
    
		scanf("%d%s%s", &val[i], a, b);
		A[i] = B[i] = C[i] = D[i] = 0;
		for (int j = 0; j < n; j++) {
    
			if (a[j] == '+')A[i] |= (1 << j);
			else if (a[j] == '-')B[i] |= (1 << j);
			if (b[j] == '-')C[i] |= (1 << j);
			else if (b[j] == '+')D[i] |= (1 << j);
		}
	}
	spfa((1 << n) - 1);
	out(dis[0] == 0x3f3f3f3f ? -1 : dis[0]);
	puts("");
	return 0;
}

By-Round Moon