代码如下

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long

using namespace std;

int n,m; 

const int INF = 1e9,N = (1<<22);

int dist[N],S,T,q[N];
bool st[N];

struct _qwq{
	int a=0,b=0,c=0,d=0;
	int cost;
}qwq[1200];

//判断该数是否能被改变 
bool judge(int state,int i)
{
	int x = qwq[i].a,y = qwq[i].b;
	int key = state&x;
	if(key != x) return false;
	if(y&state) return false;
	return true;
}

//获取改变后的值 
int get(int state,int i)
{
	int x = qwq[i].c,y = qwq[i].d;
	int ans = ~state;
	ans |= x;
	ans = ~ans;
	ans |= y;
	return ans;
}

void spfa()
{
	int hh = 0,tt = 1;
	for(int i = 0; i < N; i ++)
		dist[i] = INF,st[i] = false;
	dist[S] = 0;
	q[0] = S;
	st[S] = true;
	while(hh != tt)
	{
		int t = q[hh ++];
		if(hh == N) hh = 0;
		for(int i = 1; i <= m; i ++)
		{
			if(judge(t,i))
			{
				int j = get(t,i);
				if(dist[j] > dist[t]+qwq[i].cost)
				{
					dist[j] = dist[t] + qwq[i].cost;
					if(!st[j])
					{		
						st[j] = true;
						q[tt ++] = j;
						if(tt == N) tt = 0;	
					}	
				}	
			}	
		}	
	}	
}

int main()
{
	cin>>n>>m;
	S = (1<<n)-1,T = 0;

	for(int i = 1; i <= m; i ++)
	{
		string a,b;
		cin>>qwq[i].cost;
		cin>>a>>b;
		for(int j = 0; j < n; j ++)
		{
			if(a[j] == '+') qwq[i].a |= (1<<j);
			else if(a[j] == '-') qwq[i].b |= (1<<j);
			if(b[j] == '-') qwq[i].c |= (1<<j);
			else if(b[j] == '+') qwq[i].d |= (1<<j);			
		}
	}
	
	spfa();
	
	if(dist[T] >= INF) cout<<0<<endl;
	else cout<<dist[T]<<endl;
    return 0;
}