Luogu

分析

错误数很少，大力状压，跑一遍$\mathrm{SPFA}$即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

const int N=20+10;
const int M=100+10;
const int INF=0x3f3f3f3f;

int n,m;
int t[M];
char s1[N],s2[N];
int have[M],no[M],bring[M],kill[M];
int dis[1<<21],inq[1<<21];

inline void SPFA() {
    memset(dis,0x3f,sizeof(dis));
    queue<int> Q; Q.push((1<<n)-1);
    dis[(1<<n)-1]=0,inq[(1<<n)-1]=1;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        inq[u]=0;
        for (re int i=1;i<=m;++i) {
            if ((no[i]&(~u))!=no[i]) continue;
            if ((have[i]&u)!=have[i]) continue;
            int v=(u&(~kill[i]))|bring[i];
            if (dis[u]+t[i]<dis[v]) {
                dis[v]=dis[u]+t[i];
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
}

int main() {
    scanf("%d%d",&n,&m);
    for (re int i=1;i<=m;++i) {
        scanf("%d%s%s",&t[i],s1,s2);
        for (re int j=n-1;j>=0;--j) {
            if (s1[j]=='+') have[i]|=(1<<j);
            else if (s1[j]=='-') no[i]|=(1<<j);
            if (s2[j]=='+') bring[i]|=(1<<j);
            else if (s2[j]=='-') kill[i]|=(1<<j);
        }
    }
    SPFA();
    if (dis[0]==INF) dis[0]=0;
    printf("%d\n",dis[0]);
    return 0;
}