1.题目描述：点击打开链接
2.解题思路：本题要求找最短的时间，乍一看想用动态规划解决，但可惜这种做法是行不通的，因为状态经过多次转移之后可能会回到原先的状态，即状态图不是DAG。因此联想到用图论上的最短路算法来解决。先把每个状态都看成一个结点，然后用Dijkstra算法解决即可，不过本题与普通的最短路问题略有不同：结点很多，多达2^n个，而且很多状态根本遇不到。所以没必要先把图储存好。（一般的Dijkstra算法用之前都储存好了图）
这里可以直接枚举这m个补丁，看哪一个能用，这样既就能不断地拓展结点了。初始状态是(1<<n)-1,最终的状态是0。本题最终答案是d[0]。本题的一个技巧是先把打补丁之前的状态中必须有的bug用集合来表示，再把无所谓的bug也表示出来，都放到pre数组；用同样的方法预处理打补丁后的状态，放到Next数组中。这样后面的一系列结点就能通过集合之间的运算拓展出来了。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;#define N 21#define M 101const int INF = 500000000;int pre[2][M], Next[2][M];//pre数组存放之前的状态，Next数组存放之后的状态int t[M];int d[1 << N];typedef pair<int, int> P;void dijkstra(int n, int m)//求最短路{for (int i = 0; i < (1 << n); i++)d[i] = INF;priority_queue<P, vector<P>, greater<P> >q;d[(1 << n) – 1] = 0;//全部bug都存在为初始状态q.push(P(0, (1 << n) – 1));while (!q.empty()){P u = q.top(); q.pop();int x = u.second;if (u.first != d[x])continue;for (int i = 0; i < m;i++)if ((x | pre[0][i]) == x &&(x&pre[1][i]) == x)//枚举所有m个补丁，看是否能打上，有bug时用|，，没有用&{int v = x | Next[0][i];//求并集v &= Next[1][i];//求交集if (d[v]>d[x] + t[i]){d[v] = d[x] + t[i];q.push(P(d[v], v));}}}}int main(){//freopen("t.txt", "r", stdin);int n, m;int rnd = 0;char b1[N], b2[N];while (~scanf("%d%d", &n, &m)&& (m || n)){for (int i = 0; i < m; i++){scanf("%d %s %s", t + i, b1, b2);pre[0][i] = pre[1][i] = Next[0][i] = Next[1][i] = 0;for (int j = 0; j < n; j++){if (b1[j] == '+')pre[0][i] |= (1 << j);//pre[0]存放必须有的bug的集合if (b1[j] != '-')pre[1][i] |= (1 << j);//pre[1]存放任意状态的bug的集合，同理Next数组if (b2[j] == '+')Next[0][i] |= (1 << j);if (b2[j] != '-')Next[1][i] |= (1 << j);}}dijkstra(n, m);printf("Product %d\n", ++rnd);if (d[0] == INF)puts("Bugs cannot be fixed.");else printf("Fastest sequence takes %d seconds.\n", d[0]);puts("");}return 0;}
你并不一定会从此拥有更美好的人生，
