题意：对于一个软件有若干个bug和若干个补丁告诉你打每个补丁需要的状态和打完后的状态还有打每个补丁的费用，让你求把软件修好的最小费用。
思路：这道就是就是最短路然后再加上状态压缩存储，把+号与-号分开存在两个变量中，然后在Dijkstra执行的时候把补丁看成边，软件状态看成点就行了，别的都一样。
代码如下：
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <stack> 8 #include <utility> 9 #define ll long long 10 #define eps 1E-8 11 #define INF 5000001 12 #define LEN 111 13 14 using namespace std; 15 16 typedef pair<int, int> pii; 17 int n, m, vis[1<<21]; 18 19 struct V{ 20 int val, bfix, bocr, efix, eocr; 21 }; 22 23 V vex[LEN]; 24 25 struct S{ 26 int val, st; 27 bool operator<(const S b) const 28 {return val<b.val;} 29 }; 30 31 int BFS() 32 { 33 priority_queue<pii, vector<pii>, greater<pii> > q; 34 q.push(make_pair(0, (1<<n)-1)); 35 while(!q.empty()){ 36 pii nv= q.top(); q.pop(); 37 if(nv.second==0) return nv.first; 38 if(vis[nv.second])continue; 39 vis[nv.second] = 1; 40 for(int i=0; i<m; i++){ 41 pii xx = nv; 42 if((vex[i].bfix & xx.second)==vex[i].bfix && ((~xx.second) & vex[i].bocr)==vex[i].bocr){ 43 xx.second|=vex[i].efix; 44 xx.second&=(~vex[i].eocr); 45 xx.first += vex[i].val; 46 q.push(xx); 47 } 48 } 49 } 50 return -1; 51 } 52 53 int main() 54 { 55 // freopen("in.txt", "r", stdin); 56 57 char str[LEN]; 58 int kase = 1; 59 while(scanf("%d%d", &n, &m)!=EOF){ 60 if(n==0 && m==0) break; 61 memset(vex, 0, sizeof vex); 62 for(int i=0; i<m; i++){ 63 scanf("%d%s", &vex[i].val, str); 64 for(int j=0; j<n; j++){ 65 if(str[j]=='+')vex[i].bfix |= (1<<j); 66 } 67 for(int j=0; j<n; j++){ 68 if(str[j]=='-')vex[i].bocr |= (1<<j); 69 } 70 scanf("%s", str); 71 for(int j=0; j<n; j++){ 72 if(str[j]=='+')vex[i].efix |= (1<<j); 73 } 74 for(int j=0; j<n; j++){ 75 if(str[j]=='-')vex[i].eocr |= (1<<j); 76 } 77 } 78 memset(vis, 0, sizeof vis); 79 int ans = -1; 80 ans = BFS(); 81 printf("Product %d ", kase++); 82 if(ans == -1)printf("Bugs cannot be fixed. "); 83 else printf("Fastest sequence takes %d seconds. ", ans); 84 printf(" "); 85 } 86 return 0; 87 }