随笔-68  评论-10  文章-0  trackbacks-0

BFS+优先队列+位运算.

#include<iostream>
#include
<queue>
using namespace std;

const int inf=0x7fffffff;
int n,l,nop,nw,s,d;
char oper[35][25];
int cost[35];
char beg[22][22],end[22][22];
int hash[1050000];

typedef 
struct  node
{
    
int cst;
    
int integ;
    
bool operator< (node a) const
    
{
        
return a.cst<cst;
    }
    
}
Node;

void transf(int i,int &tt)
{
    
int j,k;
    
for(j=0;j<l;j++)
    

        k
=l-j-1;
        
if(oper[i][j]=='N'continue;
        
else if(oper[i][j]=='F') tt=tt^(1<<k);
        
else if(oper[i][j]=='S') tt=tt|(1<<k);        
        
else if(oper[i][j]=='C') tt=tt&(~(1<<k));
    }

}


void bfs(int v)
{
    priority_queue
<Node> q;
    Node temp;
    temp.cst
=0;
    temp.integ
=s;
    hash[s]
=0;
    q.push(temp);
    
int ans;
    
bool mark=false;
    
while(!q.empty())
    
{
        temp
=q.top();
        q.pop();
        
if(temp.integ==d)
        
{
            mark
=true;
            ans
=temp.cst;
            
break;
        }

        
        
for(int i=1;i<=nop;i++)
        
{
            
int tt=temp.integ;
            transf(i,tt);

            Node tp;
            tp.integ
=tt;
            tp.cst
=temp.cst+cost[i];
            
if(tp.cst<hash[tp.integ])
            
{
                hash[tp.integ]
=tp.cst;
                q.push(tp);
            }

        }

    }

    
if(mark)
    
{
        
if(v==nw) printf("%d\n",ans);
        
else printf("%d ",ans);
    }

    
else 
    
{
        
if(v==nw) printf("NP\n");
        
else printf("NP ");
    }

}


int main()
{
    
int i,v;
    scanf(
"%d",&n);
    
while(n--)
    
{
        scanf(
"%d%d%d",&l,&nop,&nw);
        
for(i=1;i<=nop;i++)
            scanf(
"%s%d",oper[i],&cost[i]);
        
for(i=1;i<=nw;i++
            scanf(
"%s%s",beg[i],end[i]);
        
for(v=1;v<=nw;v++)
        
{
            
for(i=0;i<(1<<l);i++) hash[i]=inf;
            s
=d=0;
            
for(i=0;i<l;i++)
                s
+=(beg[v][i]-48)*(1<<(l-i-1));
            
for(i=0;i<l;i++)
                d
+=(end[v][i]-48)*(1<<(l-i-1));

            bfs(v);
        }

    }

    
return 0;
}

posted on 2010-08-17 17:22 wuxu 阅读(139) 评论(0)  编辑 收藏 引用 所属分类: 搜索

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理