#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
using namespace std;

#define MaxN 1048576
#define MaxL 33
#define INF -1


struct HEAPtype
{
	long h2n;/* from Heap number To vertex Number*/
	long vop;/* Value Of Priority */
}heap[MaxN];
long n2h[MaxN];/* from vertex Number To Heap number */
long hn;/*the number of Heap Nodes*/

int Better(long ax,long bx)/* which one is better of priority */
{
	if (ax<bx || (bx==INF && ax!=INF)) return 1;
	return 0;
}
int HeapSwap(long ix,long jx)
{
	long temp;
	long vx,ux;
	if (ix>hn || jx>hn) return 0;
	temp=heap[ix].vop;	heap[ix].vop=heap[jx].vop;	heap[jx].vop=temp;
	vx=heap[ix].h2n;
	ux=heap[jx].h2n;
	temp=n2h[vx];	n2h[vx]=n2h[ux];	n2h[ux]=temp;
	temp=heap[ix].h2n;	heap[ix].h2n=heap[jx].h2n;	heap[jx].h2n=temp;
	return 0;
}
int Heapfy(long ix)
{
	long jx;
	if (ix>hn) return 0;
	/*up adjust*/
	jx=0;
	while (ix/2>=1 && Better(heap[ix].vop,heap[ix/2].vop)) 
	{
		HeapSwap(ix,ix/2);
		ix=ix/2;
		jx=1;
	}
	if (jx) return 1;
	/*else,down adjust*/
	jx=ix;
	do
	{
		ix=jx;
		if (ix*2<=hn && Better(heap[ix*2].vop,heap[ix].vop)) jx=ix*2;
		if (ix*2+1<=hn && Better(heap[ix*2+1].vop,heap[ix].vop)) jx=ix*2+1;
		if (ix!=jx) HeapSwap(ix,jx);
	}
	while (ix!=jx);
	return 0;
}
int Relax(long ix,long wt,long jx)
{
	if (Better(heap[ix].vop+wt,heap[jx].vop))
	{
		heap[jx].vop=heap[ix].vop+wt;
		Heapfy(jx);
	}
	return 0;
}

typedef struct NODES { long EW,ID; } NODE;

vector <struct NODES> al[MaxN];


int t;
int nop,nw,l;
char op[MaxL][MaxL];
long c[MaxL];
long sv,tv;
long dest;/* Shortest Path */

long i,j;
long u,v;
char bin[MaxN][MaxL];
char temps[MaxL];
int hash[MaxN];

long Convert(char sx[MaxL])
{
	int ix;
	long oct=0;
	for (ix=0;ix<l;ix++) oct=oct*2+sx[ix]-'0';
	return oct;
}
int pos[MaxN];
long Dijkstra()
{
	int ix,jx;
	int an;
	NODE tnode;
	memset(n2h,0,sizeof(n2h));
	/* Insert the Node */
	hn=1;
	heap[1].vop=0;
	heap[1].h2n=sv;
	n2h[sv]=1;
	while (hn)
	{
		if (heap[1].h2n==tv) return heap[1].vop;
		/* Take Out the Top Node of Heap */		
		heap[0].vop=heap[1].vop;/* vop will be used for relaxing*/
		u=heap[1].h2n;
		HeapSwap(1,hn);
		hn--;
		
		Heapfy(1);/* Keep Heaplike */
		memset(pos,-1,sizeof(pos));
		
		for (ix=1;hash[u]==0 && ix<=nop;ix++)
		{
			strcpy(temps,bin[u]);
			for (jx=0;jx<l;jx++)
			{
				if (op[ix][jx]=='F') temps[jx]=(temps[jx]=='1' ? '0' : '1');
				else if (op[ix][jx]=='S') temps[jx]='1';
				else if (op[ix][jx]=='C') temps[jx]='0';
			}
			v=Convert(temps);
			if (v==u) continue;
			if (bin[v][0]==0) strcpy(bin[v],temps);
			if (pos[v]>=0 && c[ix]<al[u][pos[v]].EW) al[u][pos[v]].EW=c[ix];
			if (pos[v]==-1)
			{
				tnode.EW=c[ix];
				tnode.ID=v;
				al[u].push_back(tnode);
				pos[v]=al[u].size()-1;
			}
		}		
		hash[u]=1;
		an=al[u].size()-1;
		for (ix=0;ix<=an;ix++) 
		{
			v=al[u][ix].ID;
			if (n2h[v]==0)
			{
				hn++;
				if (hn>MaxN-1) return 0;
				heap[hn].vop=INF;
				heap[hn].h2n=v;
				n2h[v]=hn;
			}
			Relax(0,al[u][ix].EW,n2h[v]);
		}
	}
	return 0;
}
int main()
{
	scanf("%d",&t);
	while (t)
	{
		scanf("%d",&l);
		memset(bin,0,sizeof(bin));
		memset(al,0,sizeof(al));
		memset(hash,0,sizeof(hash));
		scanf("%d%d\n",&nop,&nw);
		for (i=1;i<=nop;i++) scanf("%s%d",&op[i],&c[i]);
		for (i=1;i<=nw;i++)
		{
			scanf("%s",&temps);
			sv=Convert(temps);
			if (bin[sv][0]==0) strcpy(bin[sv],temps);
			scanf("%s",&temps);
			tv=Convert(temps);
			if (bin[tv][0]==0) strcpy(bin[tv],temps);
			dest=Dijkstra();
			if (dest) printf("%ld",dest);
			else printf("NP");
			if (i==nw) printf("\n");
			else printf(" ");
		}
		t--;
	}
	return 0;
}

• 谁给一些容易RE的数据啊? (0) entrails 2007-09-06 00:18:06