这个题目巧妙之处在于用二进制的每个位1,0分别表示bug的有无，以及实施补丁对相应bug的要求以及实施后的对bug的影响。
软件bug的状态：1表示相应bug仍然存在，0表示已经修复。这样可以将软件的状态用一个整数表示，例如1100（12)表示第1,2个bug存在，后面两个已经修复。
那么，对于n个bug 的软件，起点src = (1<<n)-1表示软件初始状态 111....111，终点sink = 0表示软件已经修复。
实施补丁的条件：
+-0 表示实施该补丁需要第1个bug存在，第2个bug不存在，对第三个无要求，可以用两个整数a1，a2表示，其中a1表示需要哪些bug存在，也就是对应字符串为'+'的地方，该整数的二进制位设为1，
其他位为0，这里为a1 = 100;a2表示哪些bug不能存在，对于字符串中'-'的位置a2相应二进制位设为0，其余为1，a2 = 101。这样判断某个软件当前状态（用整数x表示）是否符合实施补丁要求可以这样判断：
（x | a1） == x && （x & a2 ）==x
补丁对bug的影响：
同样用两个整数b1，b2，表示方式和前面a1，a2一样，b1同a1，即'+'位设为1,其余为0；b2同a2，非'-'都设为1，'-'设为0。对于x实施补丁的过程就变成了：y = x，y |= b1，y &= b2.这样由状态x变成了y。
因此每个状态转化为一个整数，整个问题变成球一条从src，到sink的最短路，每条路的长度就是每个补丁花费的时间，dij可破之。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <climits> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cmath> 7 #include <vector> 8 #include <queue> 9 #include <algorithm> 10 #define esp 1e-6 11 #define pb push_back 12 #define in freopen("in.txt", "r", stdin); 13 #define out freopen("out.txt", "w", stdout); 14 #define print(a) printf("%d ",(a)); 15 #define bug puts("********))))))"); 16 #define Rep(i, c) for(__typeof(c.end()) i = c.begin(); i != c.end(); i++) 17 #define inf 0x0f0f0f0f 18 using namespace std; 19 typedef long long LL; 20 typedef vector<int> VI; 21 typedef vector<int>:: iterator IT; 22 typedef pair<int, int> pii; 23 #define N 30 24 #define M 200 25 #define MAX 10000000 26 char a[N], b[N]; 27 int s[M][2], t[M][2], w[M]; 28 int d[MAX], inq[MAX]; 29 int n, m, src, sink; 30 priority_queue<pii, vector<pii>, greater<pii> > q; 31 void dij(void) 32 { 33 memset(d, 0x0f, sizeof(d)); 34 // memset(inq, 0, sizeof(inq)); 35 d[src] = 0; 36 // inq[src] = 1; 37 q.push(make_pair(d[src], src)); 38 while(!q.empty()) 39 { 40 pii u = q.top(); 41 q.pop(); 42 int x = u.second; 43 if(d[x] != u.first) 44 continue; 45 for(int i = 0; i < m; i++) 46 { 47 if(((x | s[i][0]) == x) && ((x & s[i][1]) == x)) 48 { 49 int y = x; 50 y |= t[i][0]; 51 y &= t[i][1]; 52 if(d[x] + w[i] < d[y]) 53 { 54 d[y] = d[x] + w[i]; 55 q.push(make_pair(d[y],y)); 56 } 57 } 58 } 59 } 60 } 61 int main(void) 62 { 63 int T = 1; 64 while(scanf("%d%d", &n, &m),n+m) 65 { 66 memset(s, 0, sizeof(s)); 67 memset(t, 0, sizeof(t)); 68 src = (1<<n) - 1; 69 sink = 0; 70 for(int i = 0; i < m; i++) 71 { 72 scanf("%d%s%s", &w[i], a, b); 73 for(int j = 0; j < n; j++) 74 { 75 if(a[j] == '+') 76 s[i][0] |= (1<<j); 77 if(a[j] != '-') 78 s[i][1] |= (1<<j); 79 if(b[j] == '+') 80 t[i][0] |= (1<<j); 81 if(b[j] != '-') 82 t[i][1] |= (1<<j); 83 } 84 } 85 dij(); 86 printf("Product %d ", T++); 87 if(d[0] < inf) 88 printf("Fastest sequence takes %d seconds. ", d[0]); 89 else 90 puts("Bugs cannot be fixed."); 91 puts(""); 92 } 93 return 0; 94 }