本文主要是介绍uva 658 - It's not a Bug, it's a Feature!（优先队列Dijkstra)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：uva 658 - It's not a Bug, it's a Feature!
题目大意：有一个软件，有n个bug， 然后现在有m个补丁，然后m行，分别给出补丁需要的时间，以及原始状态和修复后的状态。对于原始状态，‘-’代表不能有这个bug，‘+’代表必须有这个bug，‘0’表示可有可无；对于修复后的状态，‘-’代表可以修复这个bug，‘+”代表会新增这个bug，’0‘是不变。问说修复n个bug的最短时间。
解题思路：可以转化成最短路问题，对于每个状态可以转换成二进制（bug存不存在），然后就可以用一个数来表示，然后就可以生成一个图，建图的过程就是暴力枚举所有可能，然后再与它修复后的状态建一条边，权值为时间。求最短路用Dijkstra算法，用优先队列优化，不然会超时。
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>#define pii pair<int,int>
using namespace std;const int N = 1500000;
const int M = 30;
const int INF = 0x3f3f3f3f;struct state {int u;int d;
};struct cmp {bool operator () (const pii& a, const pii& b) {return a.first < b.first;}
};int n, m, tmp;
char s[M], b[M];
int cur, t[M], d, vis[N];
vector<state> v[N];void add(int x, int y) {state cur;cur.u = y, cur.d = d;v[x].push_back(cur);
}void dfs(int c, int *t) {if (c >= n) {int far = 0, son = 0, k;for (int i = 0; i < n; i++) {if (b[i] == '-') k = 0;else if (b[i] == '+') k = 1;else k = t[i];far = far * 2 + t[i];son = son * 2 + k;}add(far, son);return;}if (s[c] == '0') {for (t[c] = 0; t[c] < 2; t[c]++)dfs(c + 1, t);} else {if (s[c] == '+')t[c] = 1;elset[c] = 0;dfs(c + 1, t);}
}void init() {int t[N];tmp = 1 << n;for (int i = 0; i < tmp; i++) v[i].clear();for (int i = 0; i < m; i++) {scanf("%d%s%s", &d, s, b);memset(t, 0, sizeof(t));dfs(0, t);}
}void solve() {int a[N], Min, c;priority_queue< pii, vector<pii>, greater<pii> > que;memset(a, INF, sizeof(a));memset(vis, 0, sizeof(vis));a[tmp - 1] = 0;que.push(make_pair(a[tmp - 1], tmp - 1) );while ( !que.empty() ) {pii cur = que.top(); que.pop();int x = cur.second;if (vis[x]) continue;vis[x] = 1;int f = v[x].size();for (int j = 0; j < f; j++) {int y = v[x][j].u;if ( a[y] > a[x] + v[x][j].d ) {a[y] = a[x] + v[x][j].d;que.push( make_pair(a[y], y) );}}}if (a[0] == INF)printf("Bugs cannot be fixed.\n\n");elseprintf("Fastest sequence takes %d seconds.\n\n", a[0]);
}int main () {int cas = 1;while (scanf("%d%d", &n, &m), n + m) {init();printf("Product %d\n", cas++);solve();}return 0;
}
这篇关于uva 658 - It's not a Bug, it's a Feature!（优先队列Dijkstra)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
