紫书365
题目大意：给你n个全都是bug的东西，然后每次可以修复，给你修复前后的状态，问最后如果能把bug全都修复，最少需要多少时间。
思路：从最初状态开始，然后枚举bug即可。
表示priority里面的bool operator和单纯的sort的定义的大小于号是不一样的啊，如果你想用sort来计算struct从小到大的的话是这样的
struct Node{
int bugs, dist;
bool operator < (const Node &a) const{
return dist < a.dist;
}
Node(int b = , int d = ): bugs(b), dist(d){}
};
而优先队列是这样的
struct Node{
int bugs, dist;
bool operator < (const Node &a) const{
return dist > a.dist;
}
Node(int b = , int d = ): bugs(b), dist(d){}
};
区分一下大小于号就好了
//看看会不会爆int!数组会不会少了一维！
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
const int inf = 0x3f3f3f3f;
const int maxn = ( << ) + ;
const int maxm = + ;
int n, m;
int t[maxm], d[maxn];
bool vis[maxn];
char b[maxm][], e[maxm][];
struct Node{
int bugs, dist;
bool operator < (const Node &a) const{
return dist > a.dist;
}
Node(int b = , int d = ): bugs(b), dist(d){}
}; int solve(){
memset(vis, false, sizeof(vis));
memset(d, 0x3f, sizeof(d));
priority_queue<Node> que;
int tmp = ( << n) - ;
que.push(Node(tmp, ));
d[tmp] = ; vis[tmp] = ;
while (!que.empty()){
Node u = que.top(); que.pop();
if (u.bugs == ) return u.dist;
for (int i = ; i < m; i++){
int from = u.bugs;
bool flag = false;
for (int j = ; j < n; j++){
if (b[i][j] == '-' && (from & ( << j))) {flag = true; break;}
if (b[i][j] == '+' && !(from & ( << j))) {flag = true; break;}
}
if (flag) continue;
int to = from;
for (int j = ; j < n; j++){
if (e[i][j] == '-' && (from & ( << j))) to ^= << j;
if (e[i][j] == '+') to |= << j;
}
if (d[to] > d[from] + t[i] && !vis[to]){
d[to] = d[from] + t[i];
vis[to] = false;
que.push(Node(to, d[to]));
}
}
}
return -;
} int main(){
int kase = ;
while (scanf("%d%d", &n, &m) && n){
for (int i = ; i < m; i++){
scanf("%d", t + i);
scanf("%s%s", b[i], e[i]);
}
printf("Product %d\n", ++kase);
int ans = solve();
if (ans < ) printf("Bugs cannot be fixed.\n");
else printf("Fastest sequence takes %d seconds.\n", ans);
printf("\n");
}
return ;
}