1 #include <cstdio> 2 #include <queue> 3 using namespace std; 4  5 const int maxn = 20; 6 const int maxm = 100 + 5; 7 const int INF = 1000000000; 8  9 int n, m, t[maxm], vis[1 << maxn], dist[1 << maxn];10 char before[maxm][maxn + 5], after[maxm][maxn + 5];11 12 struct Node {13     int bugs, dist;14     bool operator < (const Node& rhs) const {15         return dist > rhs.dist;16     }17 };18 19 int solve() {20     priority_queue<Node> q;21     for (int i = 0; i < (1 << n); i++) { vis[i] = 0; dist[i] = INF; }22     Node start;23     start.dist = 0;24     start.bugs = (1 << n) - 1;25     dist[start.bugs] = 0;26     q.push(start);27     while (!q.empty()) {28         Node u = q.top(); q.pop();29         if (u.bugs == 0) return u.dist;30         if (vis[u.bugs]) continue;31         vis[u.bugs] = 1;32         for (int i = 0; i < m; i++) {33             bool patchable = true;34             for (int j = 0; j < n; j++) {35                 if (before[i][j] == ‘-‘ && (u.bugs >> j & 1)) {patchable = false; break; }36                 if (before[i][j] == ‘+‘ && !(u.bugs >> j & 1)) { patchable = false; break; }37             }38             if (!patchable) continue;39             Node u2;40             u2.dist = u.dist + t[i];41             u2.bugs = u.bugs;42             for (int j = 0; j < n; j++) {43                 if (after[i][j] == ‘-‘) { u2.bugs &= ~(1 << j); }44                 if (after[i][j] == ‘+‘) { u2.bugs |= (1 << j); }45             }46             int& D = dist[u2.bugs];47             if (u2.dist < D) {48                 D = u2.dist;49                 q.push(u2);50             }51         }52     }53     return -1;54 }55 56 int main() {57     int kase = 0;58     while (scanf("%d%d", &n, &m) == 2 && n) {59         for (int i = 0; i < m; i++) scanf("%d%s%s", &t[i], before[i], after[i]);60         int ans = solve();61         printf("Product %d\n", ++kase);62         if (ans < 0) printf("Bugs cannot be fixed.\n\n");63         else printf("Fastest sequence takes %d seconds.\n\n", ans);64     }65     return 0;66 }