状压最短路
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
struct Node{
int bi1, bi2, fi1, fi2;
}nd[105];
int n, m, ww[105], cnt, dis[1050005];
bool vis[1050005];
char a[25], b[25];
queue<int> d;
void spfa(){
memset(dis, 0x3f, sizeof(dis));
int uu=(1<<n)-1;
dis[uu] = 0;
d.push(uu);
vis[uu] = true;
while(!d.empty()){
int x=d.front();
d.pop();
vis[x] = false;
for(int i=1; i<=m; i++)
if((x&nd[i].bi1)==nd[i].bi1 && (x&nd[i].bi2)==0){
int tmp=x;
tmp &= ~(nd[i].fi1);
tmp |= nd[i].fi2;
if(dis[tmp]>dis[x]+ww[i]){
dis[tmp] = dis[x] + ww[i];
if(!vis[tmp]){
vis[tmp] = true;
d.push(tmp);
}
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1; i<=m; i++){
scanf("%d", &ww[i]);
scanf("%s %s", a, b);
for(int j=0; j<n; j++){
if(a[j]=='+') nd[i].bi1 |= 1<<j;
if(a[j]=='-') nd[i].bi2 |= 1<<j;
}
for(int j=0; j<n; j++){
if(b[j]=='-') nd[i].fi1 |= 1<<j;
if(b[j]=='+') nd[i].fi2 |= 1<<j;
}
}
spfa();
if(dis[0]==0x3f3f3f3f) cout<<"0"<<endl;
else cout<<dis[0]<<endl;
return 0;
}