658 - It's not a Bug, it's a Feature!

//la solución es simplemente un dijkstra, en tanto que dado un estado
//(tiempo y bugs activos) se trata de ir a todos los otros posibles estados
//por medio de los patchs dados, con bitwise, si no, sale TLE

#include <vector>
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define mp make_pair


int main(){
 int n,m;
 int best[1<<20];//arreglo donde se guardarán las mejores soluciones, recordar que para n bugs, hay 1<<n=2^n posibles estados
 int test=1;//número de test
 char aux;

 while(cin>>n>>m && n!=0){
  int completo=(1<<n)-1;//n bits en 1
 
  //respectivamente para el patch i: inhas = lo que debe tener previamente | innhas = lo que no debe tener previamente |
  //outadd= lo que se añade | outrest=lo que se quita
  vector<int> inhas(m,0),innhas(m,0),outadd(m,0),outrest(m,completo);
 
  vector<int> t(m); //los tiempos de cada patsh
 
  //lectura
  for(int i=0;i<m;i++){
    cin>>t[i];
    for(int j=0;j<n;j++){
     cin>>aux;
     if(aux=='-') innhas[i]|=1<<j;
     else if(aux=='+') inhas[i]|=1<<j;
    }
   
    for(int j=0;j<n;j++){
     cin>>aux;
     if(aux=='+') outadd[i]|=1<<j;
     else if(aux=='-') outrest[i]&=~(1<<j);
    }
  }
 
  memset(best,-1,4*(1<<n));//se pone todo el espacio necesario en 1, se multiplica por 4 porque cada int son 4 bytes
  // y metset copia una cantidad de bytes
 
  int ini=completo;
  best[ini]=0;//estado inicial
 
  //estado de la cola de prioridad, un par: <tiempo acumulado, estado actual>
  priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
  q.push(mp(0,ini));//se añade estado inicial
  int res=-1;
 
  while(!q.empty()){
    int cost=q.top().first;
    int state=q.top().second;
    q.pop();
   
    if(best[state]<cost) continue; //si este vértice es basura
    if(state==0){res=cost;break;} //si es solución
     
    //se intenta con todos los patchs
    for(int i=0;i<m;i++){
     //se verifica si el path i sirve
     bool puede=true;
     if((state&inhas[i])!=inhas[i]) puede=false;
     else if((state&innhas[i])!=0) puede=false;
    
     if(puede){
      //se crea el siguiente estado
      int next=state;
      next|=outadd[i];
      next&=outrest[i];
      int ncost=cost+t[i];
      //si el nuevo estado se relaja
      if(best[next]==-1||best[next]>ncost){
    best[next]=ncost;
    q.push(mp(ncost,next));
      }
     }
    }
  }
 
  cout<<"Product "<<test++<<endl;
  if(res!=-1) cout<<"Fastest sequence takes "<<res<<" seconds."<<endl;
  else cout<<"Bugs cannot be fixed."<<endl;
  cout<<endl;
 }
}