洛谷(软件补丁问题)

链接：https://www.luogu.org/problemnew/show/P2761
思路：状压最短路，首先将b1,b2,f1,f2压入一个数组中，用来表示转移条件，然后初始状态是(1<<n)-1，枚举所有的补丁，满足条件的话就转移，按照dij最短路写就好了，注意括号优先级和位运算的一些细节。

#include<bits/stdc++.h>
using namespace std;

const int maxn = (1<<20)+10;
const int INF = 1e9;
int b1[maxn],b2[maxn],f1[maxn],f2[maxn];
int d[maxn];
int cost[101];
int n,m;

typedef pair<int,int> P;

void dij(int s){
    for(int i=0;i<maxn;i++)d[i] = INF;
    priority_queue<P,vector<P>,greater<P> > q;
    q.push({0,s});
    d[s] = 0;
    while(!q.empty()){
        P p = q.top();
        q.pop();
        int u = p.second;
        if(d[u]<p.first)continue;
        for(int i=0;i<m;i++){
            int flag = 0;
            for(int j=0;j<n;j++){
                if(b1[i]&(1<<j)){
                    if((u&(1<<j))==0){
                    flag = 1;
                    break;
                    }
                }
                if(b2[i]&(1<<j)){
                    if(u&(1<<j)){
                    flag = 1;
                    break;
                    }
                }
            }
            if(flag)continue;
            int v = u;
            for(int j=0;j<n;j++){
                if((f1[i]&(1<<j))&&(v&(1<<j)))v^=(1<<j);
                else if((f2[i]&(1<<j))&&(v&(1<<j))==0)v|=(1<<j);
            }
              if(d[v]>d[u] + cost[i]){
                d[v] = d[u] + cost[i];
                q.push(P{d[v],v});
            }
        }
    }
}

char str1[100],str2[100];

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%s%s",&cost[i],str1,str2);
        int n1 = strlen(str1);
        int n2 = strlen(str2);
        for(int j=0;j<n1;j++){
            if(str1[j]=='+')b1[i]|=(1<<j);
            else if(str1[j]=='-')b2[i]|=(1<<j);
        }
        for(int j=0;j<n2;j++){
            if(str2[j]=='-')f1[i]|=(1<<j);
            else if(str2[j]=='+')f2[i]|=(1<<j);
        }
    }
   /* for(int i=0;i<n;i++){
        printf("%d %d %d %d\n",b1[i],b2[i],f1[i],f2[i]);
    }*/
    int all = (1<<n) - 1;
    dij(all);
    printf("%d\n",d[0]==INF?0:d[0]);    
    return 0;
}