状态压缩+优先级bfs。

1 /* 1818 */  2 #include 
     
        3 #include 
      
         4 #include 
       
          5 #include 
        
           6 #include 
         
            7 #include 
          
            8 using namespace std; 9 10 #define MAXM 105 11 12 typedef struct { 13 int t; 14 int bm, bp; // before minus/plus 15 int am, ap; // after minus/plus 16 } patch_t; 17 18 typedef struct node_t { 19 int v, t; 20 node_t() {} 21 node_t(int vv, int tt) { 22 v = vv; t = tt; 23 } 24 friend bool operator <(const node_t &a, const node_t &b) { 25 return a.t > b.t; 26 } 27 } node_t; 28 29 int n, m; 30 patch_t patch[MAXM]; 31 int visit[1<<20]; 32 char bs[25], as[25]; 33 34 int bfs() { 35 int i, j, k; 36 int v, t; 37 node_t nd = node_t((1<
           
             Q; 39 40 memset(visit, 0x3f, sizeof(int)*(1<
            
             << (n-1-j)); 83 else if (bs[j] == '-') 84 patch[i].bm |= (1 << (n-1-j)); 85 86 } 87 // handle after str 88 for (j=0; j
             
              << (n-1-j)); 91 else if (as[j] == '-') 92 patch[i].am |= (1 << (n-1-j)); 93 94 } 95 } 96 k = bfs(); 97 if (k < 0) 98 printf("Product %d\nBugs cannot be fixed.\n\n", ++t); 99 else100 printf("Product %d\nFastest sequence takes %d seconds.\n\n", ++t, k);101 }102 103 return 0;104 }