#include<cstdio>
#include<memory.h>
#include<algorithm>
using namespace std;
#define SIZE 5000000

unsigned clear[21] = {0x0,0xFFFFFFFE,0xFFFFFFFD,0xFFFFFFFB,0xFFFFFFF7,0xFFFFFFEF,
                  0xFFFFFFDF,0xFFFFFFBF,0xFFFFFF7F,0xFFFFFEFF,0xFFFFFDFF,
                  0xFFFFFBFF,0xFFFFF7FF,0xFFFFEFFF,0xFFFFDFFF,0xFFFFBFFF,
                  0xFFFF7FFF,0xFFFEFFFF,0xFFFDFFFF,0xFFFBFFFF,0xFFF7FFFF};  //清零整数某一位要用
struct Queue{
	int value;
	int f;
}queue[SIZE];
int tail,len;
int flag[1050000];
void exch(int i,int j)                 //交换队列中的元素
{
	int tv = queue[i].value;
	int tf = queue[i].f;
	queue[i].value = queue[j].value;
	queue[i].f = queue[j].f;
	queue[j].value = tv;
	queue[j].f = tf;
}
void push(int vl,int s)               //入堆操作
{
	queue[++tail].value = vl;
	queue[tail].f = s;
	int k = tail;
	while(k > 1){
		if(queue[k].value < queue[k/2].value)
			exch(k,k/2),k /= 2;
		else
			break;
	}
}
void pop(int &vl,int &f)             //出堆操作
{
	vl = queue[1].value;
	f = queue[1].f;
	queue[1].f = queue[tail].f ;
	queue[1].value = queue[tail--].value ;
	int k = 1,e;
	while(k*2 <= tail){
		e = 2*k;
		if(queue[e+1].value < queue[e].value && e+1 <= tail)
			e++;
		if(queue[e].value < queue[k].value)
			exch(k,e),k = e;
		else
			break;
	}
}
struct Op{
	char id[21];
	int val;
}op[35];
int nop;
int adjust(int f,int j)                    //根据操作序列计算操作结果，用整数保存状态，所以用位运算
{
	int t;
	for(int i = 0; i < len; i++){
		if(op[j].id[i] == 'N')
			continue;
		if(op[j].id[i] == 'C')
			f = f&clear[len-i];           //清零
		else{
			t = 1 << (len-i-1);
			if(op[j].id[i] == 'F')
				f = f^t;             //取反
			else 
				f = f|t;              //置1
		}
	}
	return f;
}
int bfs(int s,int t)           //开始广搜
{
	int i;
	tail = 0;
	memset(flag,-1,sizeof(flag));  //flag记录某一状态是否出现过，出现过的话记录其出现所花费的最小费用
	push(0,s);
	flag[s] = 0;
	while(tail > 0){
		int tv,tf;             
		pop(tv,tf);
		for(i = 0; i < nop; i++){
			int ttv = tv + op[i].val;
			int ttf = adjust(tf,i);      //调整状态
			if(ttf == t)
				return ttv;
			if(flag[ttf] == -1 || flag[ttf] > ttv){ //如果某状态出现过，现在再次出现且花费比以前出现的大或相等，就没有必要再入队列了。
				flag[ttf] = ttv;
				push(ttv,ttf);
			}
		}
	}
	return -1;
}
bool cmp(const Op &a,const Op &b)
{
	return a.val < b.val;
}
int main()
{
	int T,nw,i,out[21],s,t,j;
	char ts[21];
	for(scanf("%d",&T); T; T--){
		scanf("%d%d%d",&len,&nop,&nw);
		for(i = 0; i < nop; i++)
			scanf("%s%d",op[i].id,&op[i].val);
		sort(op,op+nop,cmp);   //对各种操作按花费从小到大排一下序。
		for(i = 0; i < nw; i++){
			scanf("%s",ts);
			s = 0;
			for(j = 0; j < len; j++)
				s = s*2+ts[j]-'0';
			scanf("%s",ts);
			t = 0;
			for(j = 0; j < len; j++)
				t = t*2+ts[j]-'0';
			if(s == t)
				out[i] = 0;     //如果源和目标相等，则花费为0
			else
				out[i] = bfs(s,t);
		}
		if(out[0] == -1)                //以下为输出操作。
			printf("NP");
		else printf("%d",out[0]);
		for(i = 1; i < nw; i++)
			if(out[i] == -1)
				printf(" NP");
			else
				printf(" %d",out[i]);
			printf("\n");
	}
	return 0;
}

• 怎么没人帮忙看一下吗？ (3360) ACM06021fly 2006-10-14 21:07:48