记录编号	572317	评测结果	AAAAAAAA
题目名称	软件补丁	最终得分	100
用户昵称	该账号已注销	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-06-30 16:42:07	内存使用	0.00 MiB

#include<bits/stdc++.h>
using namespace std;
struct bd{
    int c1,c2,f2,f1,t;
}b[110];
int n,m,dis[(1<<20)-1];
queue<int>q;
bool v[(1<<20)-1]={0};
int SPFA()
{
    memset(dis,0x3f,sizeof(dis));
    dis[(1<<n)-1]=0;
    q.push((1<<n)-1);
    while(!q.empty()){
        int ver=q.front();
        q.pop();
        v[ver]=0;
        for(int i=1;i<=m;i++){
            if((ver&b[i].c1)==b[i].c1&&(ver&b[i].c2)==0){
                int nxt=((ver|b[i].f1)^b[i].f1)|b[i].f2;
                if(dis[nxt]>dis[ver]+b[i].t){
                    dis[nxt]=dis[ver]+b[i].t;
                    if(v[nxt]==0){
                        q.push(nxt);
                        v[nxt]=1;
                    }
                }
            }
        }
    }
    if(dis[0]==0x3f3f3f3f){
        cout<<-1<<endl;
        return 0;
    }
    else{
        cout<<dis[0]<<endl;
        return 0;
    }
}
int main(){
    freopen("bugs.in","r",stdin);
    freopen("bugs.out","w",stdout);
    cin>>n>>m;
    memset(b,0,sizeof(b));
    for(int i=1;i<=m;i++){
        int x;
        string s1,s2;
        cin>>x>>s1>>s2;
        b[i].t=x;
        for(int j=0;j<s1.length();j++){
            if(s1[j]=='+')b[i].c1+=(1<<j);
            else if(s1[j]=='-')b[i].c2+=(1<<j);
        }
        for(int j=0;j<s2.length();j++){
            if(s2[j]=='-')b[i].f1+=(1<<j);
            else if(s2[j]=='+')b[i].f2+=(1<<j);
        }
    }
    SPFA();
    return 0;
}