Source Code

Problem: 1482  User: yzhw 
Memory: 9648K  Time: 297MS 
Language: GCC  Result: Accepted 

Source Code 
# include <stdio.h>
# include <stdbool.h>
struct
{
  int o1,o2,l1,l2,len;
}data[101];
int sta[1100000],q[1100000],s=-1,e=-1;
bool inqueue[1100000];
int l,n;
int empty()
{
   return s==e&&s!=-1;
}
void push(int num)
{
   e=(e+1)%1100000;
   q[e]=num;
}
int pop()
{
    s=(s+1)%1100000;
    return q[s];
}
void dp(int ori)
{
   sta[ori]=0;
   push(ori);
   inqueue[ori]=1;
   while(!empty())
   {
     int top=pop(),i;
     inqueue[top]=0;
     for(i=0;i<n;i++)
       if((top|data[i].o1)==top&&(top&data[i].o2)==top)
       {
         int now=top;
         now|=data[i].l1;
         now&=data[i].l2;
         if(sta[now]>sta[top]+data[i].len)
         {
            sta[now]=sta[top]+data[i].len;
            if(!inqueue[now])
              {
                 push(now);
                 inqueue[now]=1;
              }
         }
       }
    }
}
int main()
{
   int testcase=1;
   while(1)
   {
     int i,j,maxnum;
     scanf("%d %d",&l,&n);
     if(!l&&!n) break;
     maxnum=(1<<l);
     for(i=0;i<maxnum;i++)
        sta[i]=0xfffffff,inqueue[i]=0;
     for(i=0;i<n;i++)
     {
       char str1[110],str2[110];
       scanf("%d %s %s",&data[i].len,str1,str2);
       data[i].o1=data[i].o2=data[i].l1=data[i].l2=0;
       for(j=l-1;j>=0;j--)
       {
         switch(str1[j])
         {
            case '0':
                 data[i].o1|=0;
                 data[i].o2|=1;
                 break;
            case '+':
                 data[i].o1|=1;
                 data[i].o2|=1;
                 break;
            case '-':
                 data[i].o1|=0;
                 data[i].o2|=0;
         };
         if(j)
         {
            data[i].o1<<=1;
            data[i].o2<<=1;
         }
       }
       for(j=l-1;j>=0;j--)
       {
         switch(str2[j])
         {
            case '0':
                 data[i].l1|=0;
                 data[i].l2|=1;
                 break;
            case '+':
                 data[i].l1|=1;
                 data[i].l2|=1;
                 break;
            case '-':
                 data[i].l1|=0;
                 data[i].l2|=0;
         };
         if(j)
         {
            data[i].l1<<=1;
            data[i].l2<<=1;
         }
       } 
     }
     dp(maxnum-1);
     printf("Product %d\n",testcase++);
     if(sta[0]==0xfffffff)
       printf("Bugs cannot be fixed.\n");
     else
       printf("Fastest sequence takes %d seconds.\n",sta[0]);
     printf("\n");
   }
  // system("pause");
   return 0;
}