首页 > 代码库 > UVa 658 (Dijkstra) It's not a Bug, it's a Feature!
UVa 658 (Dijkstra) It's not a Bug, it's a Feature!
题意：
有n个BUG和m个补丁，每个补丁用一个串表示打补丁前的状态要满足的要求，第二个串表示打完后对补丁的影响，还有打补丁所需要的时间。
求修复所有BUG的最短时间。
分析：
可以用n个二进制位表示这n个BUG的当前状态。最开始时所有BUG都存在，所以状态为n个1.目标状态是0
当打上一个补丁时，状态就会发生转移。因为有可能一个补丁要打多次，所以这个图不是DAG。
可以用Dijkstra算法，求起始状态到终态的最短路。代码中用了优先队列优化。
1 #include <cstdio> 2 #include <queue> 3 #include <cstring> 4 using namespace std; 5 6 const int maxn = 20; 7 const int maxm = 100 + 10; 8 const int INF = 1000000000; 9 10 int n, m, t[maxm], dist[1<<maxn], mark[1<<maxn];11 char before[maxm][maxn + 5], after[maxm][maxn + 5];12 13 struct Node14 {15 int bugs, dist;16 bool operator < (const Node& rhs) const17 {//优先级大的排在前面，老是弄错=_=||18 return dist > rhs.dist;19 }20 };21 22 int solve()23 {24 for(int i = 0; i < (1<<n); ++i) { dist[i] = INF; mark[i] = 0; }25 priority_queue<Node> q;26 27 Node start;28 start.dist = 0;29 start.bugs = (1<<n) - 1;30 31 dist[start.bugs] = 0;32 q.push(start);33 34 while(!q.empty())35 {36 Node u = q.top(); q.pop();37 if(u.bugs == 0) return u.dist;38 if(mark[u.bugs]) continue;39 mark[u.bugs] = 1;40 for(int i = 0; i < m; ++i)41 {42 bool flag = true;43 for(int j = 0; j < n; ++j)44 {//是否满足打补丁的条件45 if(before[i][j] == ‘+‘ && !(u.bugs & (1<<j))) { flag = false; break; }46 if(before[i][j] == ‘-‘ && u.bugs & (1<<j) ) { flag = false; break; }47 }48 if(!flag) continue;49 50 Node u2;51 u2.dist = u.dist + t[i];52 u2.bugs = u.bugs;53 for(int j = 0; j < n; ++j)54 {//打完补丁以后的状态55 if(after[i][j] == ‘+‘) u2.bugs |= (1 << j);56 if(after[i][j] == ‘-‘) u2.bugs &= ~(1 << j);57 }58 int &D = dist[u2.bugs];59 if(u2.dist < D)60 {61 D = u2.dist;62 q.push(u2);63 }64 }65 }66 67 return -1;68 }69 70 int main()71 {72 //freopen("in.txt", "r", stdin);73 74 int kase = 0;75 while(scanf("%d%d", &n, &m) == 2 && n && m)76 {77 for(int i = 0; i < m; ++i) scanf("%d%s%s", &t[i], before[i], after[i]);78 int ans = solve();79 printf("Product %d\n", ++kase);80 if(ans < 0) puts("Bugs cannot be fixed.\n");81 else printf("Fastest sequence takes %d seconds.\n\n", ans);82 }83 84 return 0;85 }
UVa 658 (Dijkstra) It's not a Bug, it's a Feature!
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。