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 阅读(106)
评论(0) 编辑 收藏 引用 所属分类:
搜索