2692988_re.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

#define MAX 10000
using namespace std;

int l, a, b;
struct Node
{
	char change[21];
	int cost;
}oper[33];

char st[21], ed[21];

typedef struct node
{
	int cost;
	char status[21];
}Queue;

Queue que[MAX];
int f, r;
int mark[1<<20];

int turn(int p,char str[],char tmp[])
{
	int i, t, sum, base;

	sum = 0;base = 1;
	if(p>=0)
	{
		for(i = 0; i < l; i++)
		{
			switch(oper[p].change[i])
			{
			case 'F': t = !(str[i]-'0');break;
			case 'S': t = 1;break;
			case 'C': t = 0;break;
			default: t = str[i]-'0';
			}
			tmp[i] = t+'0';
		}
	}
	for(i = 0; i < l; i++)
	{
		sum += base*(tmp[i]-'0');
		base *= 2;
	}
	return sum;
}

bool less(Queue c,Queue d)
{
	return c.cost>d.cost;
}

void bfs()
{
	int i, w, t, end;
	char tmp[21], str[21];

	f = r = -1;
	que[++r].cost = 0;
	strcpy(que[r].status,st);
	memset(mark,0,sizeof(mark));
	mark[turn(-1,str,st)] = 1;
	end = turn(-1,str,ed);
	while (f!=r)
	{
		++f;
		w = que[f].cost;
		strcpy(str,que[f].status);
		for (i = 0; i < a; i++)
		{
			t = turn(i,str,tmp);
			if(!mark[t])
			{
				mark[t] = 1;
				if(t==end)
				{
					printf("%d ",w+oper[i].cost);
					goto over;
				}
				que[++r].cost = w+oper[i].cost;
				strcpy(que[r].status,tmp);
				push_heap(&que[f+1],&que[r],less);
			}
		}
	}
	printf("NP ");
over:
	;
}

bool cmp(struct Node c,struct Node d)
{
	return c.cost<d.cost;
}

int main()
{
	int t, i;

	scanf("%d",&t);
	while (t--)
	{
		scanf("%d%d%d",&l,&a,&b);
		for (i = 0; i < a; i++)
			scanf("%s%d",oper[i].change,&oper[i].cost);
		sort(oper,oper+a,cmp);
		for (i = 0; i < b; i++)
		{
			scanf("%s%s",st,ed);
			if(strcmp(st,ed)==0)
				printf("0\n");
			else
				bfs();
		}
		printf("\n");
	}
	return 0;
}