青岛建站模板厂家,做公众号商城原型的网站,wordpress产品页名称,成都网站网页设计题意
给出一个包含n个bug的应用程序#xff0c;以及m个补丁#xff0c;每个补丁使用两个字符串表示#xff0c;第一个串表示补丁针对bug的情况#xff0c;即哪些bug存在#xff0c;以及哪些bug不存在#xff0c;第二个串表示补丁对bug的修复情况#xff0c;即修复了哪些…题意
给出一个包含n个bug的应用程序以及m个补丁每个补丁使用两个字符串表示第一个串表示补丁针对bug的情况即哪些bug存在以及哪些bug不存在第二个串表示补丁对bug的修复情况即修复了哪些bug,以及引入哪些bug。补丁还包含修复的时间。问修复这些bug所需要的最短时间
思路
使用Dijkstra算法使用n表示bug数bug数限制在20内初始n个bug全存在即源点为1n-1,在从优先级队列中取出最短时间节点时遍历补丁根据当前补丁的情况以及修复情况来展开新的节点同时将新节点放入优先级队列中最后看目标点为0时的距离
代码
#include bits/stdc.husing 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;vectorPatch patches;bool done[SZV];int d[SZV];void init(int n){this- n (1 n);patches.clear();}void dijkstra(int s){priority_queueHeapNode 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);}}
}DijkstraMAXV, 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;
}
注意
因为在代码中初始节点数为120-1如果直接在栈上即main函数中创建Dijkstra类由于栈空间限制会出错所以需要设置为全局变量
