UVa658 It’s not a Bug, it’s a Feature!(Dijkstra)

题意

给出一个包含n个bug的应用程序，以及m个补丁，每个补丁使用两个字符串表示，第一个串表示补丁针对bug的情况，即哪些bug存在，以及哪些bug不存在，第二个串表示补丁对bug的修复情况，即修复了哪些bug,以及引入哪些bug。补丁还包含修复的时间。问修复这些bug所需要的最短时间

思路

使用Dijkstra算法，使用n表示bug数，bug数限制在20内，初始n个bug全存在，即源点为1<<n-1,在从优先级队列中取出最短时间节点时，遍历补丁，根据当前补丁的情况以及修复情况来展开新的节点，同时将新节点放入优先级队列中，最后看目标点为0时的距离

代码

#include <bits/stdc++.h>using namespace std;#define _for(i, a, b) for(int i = (a); i < (b); i++)
#define _rep(i, a, b) for (int i = (a); i <= (b); i++)struct Edge
{int from, to, dist;
};struct HeapNode
{int u, d;bool operator<(const HeapNode& other) const{return d > other.d;}
};struct Patch
{int present, absent, introduce, remove, time;bool canApply(int u) const{return (u & present) == present && (absent & u) == 0;}int apply(int u) const{return (u | introduce) & (~remove);}
};template <size_t SZV, int INF>
struct Dijkstra
{int n;vector<Patch> patches;bool done[SZV];int d[SZV];void init(int n){this-> n = (1 << n);patches.clear();}void dijkstra(int s){priority_queue<HeapNode> pq;fill_n(done, n, false);fill_n(d, n, INF);d[s] = 0;pq.push({s, 0});while (!pq.empty()) {HeapNode curNode = pq.top();pq.pop();int u = curNode.u;if (done[u]) {continue;}done[u] = true;_for(i, 0, patches.size()) {const Patch& p = patches[i];if (!p.canApply(u)) {continue;}int v = p.apply(u);if (d[v] > d[u] + p.time) {d[v] = d[u] + p.time;pq.push({v, d[v]});}}}}
};void fastio()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
}const int MAXN = 20;
const int MAXV = (1 << MAXN) + 4;
const int INF = 1e9;int n, m;void toInt(const string& s, int& i1, int& i2)
{i1 = i2 = 0;_for(i, 0, n) {if (s[i] == '+') {i1 |= (1 << i);}if (s[i] == '-') {i2 |= (1 << i);}}
}Dijkstra<MAXV, INF> solver;int main()
{fastio();#ifndef ONLINE_JUDGEifstream fin("f:\\OJ\\uva_in.txt");streambuf* back = cin.rdbuf(fin.rdbuf());#endifint kase = 1;while (cin >> n >> m) {if (n == 0 && m == 0) {break;}//cout << "n:" << n << " m:" << m << endl;solver.init(n);string buf1, buf2;Patch patch;_for(i, 0, m) {cin >> patch.time >> buf1 >> buf2;toInt(buf1, patch.present, patch.absent);toInt(buf2, patch.introduce, patch.remove);solver.patches.push_back(patch);}/*for (int i = 0; i < solver.patches.size(); i++) {const Patch& patch = solver.patches[i];cout << patch.present << " " << patch.absent << " " << patch.introduce << " " << patch.remove << endl;}*/solver.dijkstra(solver.n - 1);cout << "Product " << kase++ << endl;if (solver.d[0] == INF) {cout << "Bugs cannot be fixed." << endl;} else {cout << "Fastest sequence takes " << solver.d[0] << " seconds." << endl;}cout << endl;}#ifndef ONLINE_JUDGEcin.rdbuf(back);#endifreturn 0;
}

注意

因为在代码中初始节点数为1<<20-1，如果直接在栈上即main函数中创建Dijkstra类，由于栈空间限制，会出错，所以需要设置为全局变量