记录编号	572316	评测结果	AAAAAAAA
题目名称	软件补丁	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-06-30 16:34:13	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=(1<<20)+5;
const int M=100+5;
int n,m;
int a[M],b[M],x[M],y[M];
int v[M];
char s1[25],s2[25];
int d[N];
bool vis[N]={0};
struct sdf{
    int pt,dist;
	bool operator<(const sdf&x)const{
		return x.dist<dist;
	}
};
void dij(){
    memset(d,0x3f,sizeof(d));
    priority_queue<sdf>q;
    d[(1<<n)-1]=0;
    q.push({(1<<n)-1,0});
    while(!q.empty()){
        int pt=q.top().pt;
        q.pop();
        if (vis[pt]==1)continue;
        vis[pt]=1;
        for (int i=1;i<=m;i++){
            if ((pt&a[i])==a[i]&&(pt&b[i])==0){
                int nxt=((pt|x[i])^x[i])|y[i];
                if (v[i]+d[pt]<d[nxt]){
                    d[nxt]=v[i]+d[pt];
                    q.push({nxt,d[nxt]});
                }
            }
        }
    }
    if (d[0]==1061109567){
        printf("-1\n");
    }
    else{
        printf("%d\n",d[0]);
    }
    return ;
}
int main(){
    freopen ("bugs.in","r",stdin);
    freopen ("bugs.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        scanf("%d",&v[i]);
        scanf("%s%s",s1,s2);
        for (int j=0;j<strlen(s1);j++){
            if (s1[j]=='+')a[i]+=(1<<j);
            if (s1[j]=='-')b[i]+=(1<<j);
        }
        for (int j=0;j<strlen(s2);j++){
            if (s2[j]=='-')x[i]+=(1<<j);
            if (s2[j]=='+')y[i]+=(1<<j);
        }
    }
    dij();
    return 0;
}