2699081_wa.cpp

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

#include <stdio.h>
#include <algorithm>
#define INF 2100000000
#define MAX 1000000
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], dis[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, u, start, end, tt;
	Queue t;
	char tmp[21], str[21];

    r = 0;
    for (i = 0; i < (1<<l); i++)
        dis[i] = INF;
	que[r].cost = 0;
	strcpy(que[r].status,st);
	memset(mark,0,sizeof(mark));
	start = turn(-1,str,st);
	end = turn(-1,str,ed);
	dis[start] = 0;
	r++;
	while (r>=0&&!mark[end])
	{
		t = que[0];
		u = turn(-1,str,t.status);
		pop_heap(que,que+r,less);
		r--;
		if (u==end)
		{
           printf("%d ",t.cost);      
           return ;      
        }
		if (mark[u]==1) 
		   continue;
        mark[u] = 1;
        for (i = 0; i < l; i++)
        {
            tt = turn(i,t.status,tmp);
            if (!mark[tt]&&dis[u]+oper[i].cost<dis[tt])
            {
               dis[tt] = oper[i].cost+dis[u];
               que[r].cost = dis[tt];
               strcpy(que[r].status,tmp);
               r++;
               push_heap(que,que+r,less);
            }
        }
	}
	printf("NP ");
}

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;
}