P2761 软件补丁问题 参考代码

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

typedef long long LL;
const int maxn = (1 << 20) + 100;
const int maxm = 100 + 100;
const LL INF = 0x3f3f3f3f3f3f3f3f;
struct Node {
    int pos;
    LL dis;
};

bool operator<(const Node &a, const Node &b) {
    return a.dis > b.dis;
}

struct Edge {
    LL dis;
    int b1, b2, f1, f2;

    Edge() {}

    Edge(const string &s1, const string &s2, LL dis) : dis(dis) {
        b1 = b2 = f1 = f2 = 0;
        for (int i = 0; i < (int) s1.length(); ++i) {
            if (s1[i] == '+') {
                b1 |= 1 << i;
            }
            if (s1[i] == '-') {
                b2 |= 1 << i;
            }
        }
        for (int i = 0; i < (int) s2.length(); ++i) {
            if (s2[i] == '-') {
                f1 |= 1 << i;
            }
            if (s2[i] == '+') {
                f2 |= 1 << i;
            }
        }
    }

    Node get(int pos) {
        if ((pos & b1) == b1 && (pos & (~b2)) == pos) {
            return {(pos & (~f1)) | f2, dis};
        }
        return {0, INF};
    }
};

int n, m, w;
bool vis[maxn];
LL dis[maxn];
string s1, s2;
Edge edge[maxm];
priority_queue<Node> que;

void dij(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    que.push({s, 0});
    while (!que.empty()) {
        Node tmp = que.top();
        que.pop();
        if (vis[tmp.pos]) {
            continue;
        }
        vis[tmp.pos] = true;
        for (int i = 0; i < m; ++i) {
            Node node = edge[i].get(tmp.pos);
            if (dis[node.pos] > dis[tmp.pos] + node.dis) {
                dis[node.pos] = dis[tmp.pos] + node.dis;
                que.push({node.pos, dis[node.pos]});
            }
        }
    }
}

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> w >> s1 >> s2;
        edge[i] = Edge(s1, s2, w);
    }
    dij((1 << n) - 1);
    cout << (dis[0] == INF ? 0 : dis[0]) << endl;

    return 0;
}