还有就是用链表好像比数组慢得多，但我改成数组后还是TLE啊TLE

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define MaxN 2000023
#define INF 0x7FFFFFFFFFFFFFFF

int n;
int sv,tv;

struct NODE
{
	int ID;
	__int64 EW;
}a[MaxN][3];
int an[MaxN];

struct HeapType{__int64 vop;int h2n;} heap[MaxN];
int n2h[MaxN];
int hn;

int HeapSwap(int ix,int jx)
{
	__int64 temp;
	int vx,ux;
	int tempv;
	temp=heap[ix].vop;	heap[ix].vop=heap[jx].vop;	heap[jx].vop=temp;

	vx=heap[ix].h2n;
	ux=heap[jx].h2n;

	tempv=n2h[vx];		n2h[vx]=n2h[ux];			n2h[ux]=tempv;
	tempv=heap[ix].h2n;	heap[ix].h2n=heap[jx].h2n;	heap[jx].h2n=tempv;
	return 0;
}
int Heapify(int ix)
{
	int jx;
	/*up adjust*/
	jx=0;
	while (ix/2>=1 && heap[ix].vop<heap[ix/2].vop)
	{
		HeapSwap(ix,ix/2);
		ix=ix/2;
	}
	/*else,down adjust*/
	jx=ix;
	do
	{
		ix=jx;
		if (ix*2<=hn && heap[ix*2].vop<heap[ix].vop) jx=ix*2;
		if (ix*2+1<=hn && 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(int ix,__int64 wt,int jx)
{
	if (heap[ix].vop+wt<heap[jx].vop)
	{
		heap[jx].vop=heap[ix].vop+wt;
		Heapify(jx);
	}
	return 0;
}
__int64 Dijkstra()
{
	int ix;
	int ux,vx;
	memset(n2h,-1,sizeof(n2h));
	hn=1;
	n2h[sv]=hn;
	heap[n2h[sv]].vop=0;
	heap[n2h[sv]].h2n=sv;
	while (hn)
	{
		if (heap[1].h2n==tv) return heap[1].vop;
		heap[0].vop=heap[1].vop;
		ux=heap[1].h2n;
		HeapSwap(1,hn);
		hn--;
		Heapify(1);
		n2h[ux]=0;
		for (ix=0;ix<=an[ux];ix++)
		{
			vx=a[ux][ix].ID;
			if (n2h[vx]==-1)
			{
				hn++;
				n2h[vx]=hn;
				heap[n2h[vx]].h2n=vx;
				heap[n2h[vx]].vop=INF;
			}
			if (n2h[vx]) Relax(0,a[ux][ix].EW,n2h[vx]);
		}
	}
	return INF;
}
int InsertNode(int ux,int vx,__int64 wtxx)
{
	an[ux]++;
	a[ux][an[ux]].ID=vx;
	a[ux][an[ux]].EW=wtxx;
	return 0;
}
int GetData()
{
	int ns;
	int u;
	__int64 wtx;
	int sf,tf,sbt;
	n=0;
	scanf("%d",&n);
	if (n==0) return 0;
	memset(a,0,sizeof(a));
	memset(an,0,sizeof(an));
	n++;
	scanf("%d%d",&ns,&u);
	sv=ns*n+u+1;
	scanf("%d%d",&ns,&u);
	tv=ns*n+u+1;
	if ((sv-1)%n<(tv-1)%n) sbt=1;
	else sbt=0;
	sf=(sv-1)%n+1;
	tf=(tv-1)%n+1;
	if (!sbt)
	{
		sf=(tv-1)%n+1;
		tf=(sv-1)%n+1;
	}
	for (u=1;u<=n-1;u++)
	{
		scanf("%I64d",&wtx);
		if (u>=sf && u<=tf-1)
		{
			if (sbt) InsertNode(u,u+1,wtx);
			else InsertNode(u+1,u,wtx);		
		}
		else if (u<sf)
		{
			if ((sbt && (sv-1)/n==0) || (!sbt && (tv-1)/n==1)) InsertNode(u+1,u,wtx);
			else InsertNode(u,u+1,wtx);
		}
		else
		{
			if ((sbt && (tv-1)/n==0) || (!sbt && (sv-1)/n==1)) InsertNode(u+1,u,wtx);
			else InsertNode(u,u+1,wtx);
		}
	}
	for (u=1;u<=n;u++)
	{
		scanf("%I64d",&wtx);
		if (u<=sf)
		{
			if ((sbt && (sv-1)/n==0) || (!sbt && (tv-1)/n==1)) InsertNode(u,n+u,wtx);
			else InsertNode(n+u,u,wtx);
		}
		else if (u>=tf)
		{
			if ((sbt && (tv-1)/n==1) || (!sbt && (sv-1)/n==0)) InsertNode(u,n+u,wtx);
			else InsertNode(n+u,u,wtx);
		}
		else
		{
			InsertNode(u,n+u,wtx);
			InsertNode(n+u,u,wtx);
		}
	}
	for (u=1;u<=n-1;u++)
	{
		scanf("%I64d",&wtx);
		if (u>=sf && u<=tf-1)
		{
			if (sbt) InsertNode(n+u,n+u+1,wtx);
			else InsertNode(n+u+1,n+u,wtx);		
		}
		else if (u<sf)
		{
			if ((sbt && (sv-1)/n==0) || (!sbt && (tv-1)/n==1)) InsertNode(n+u,n+u+1,wtx);
			else InsertNode(n+u+1,n+u,wtx);
		}
		else
		{
			if ((sbt && (tv-1)/n==0) || (!sbt && (sv-1)/n==1)) InsertNode(n+u,n+u+1,wtx);
			else InsertNode(n+u+1,n+u,wtx);
		}
	}
	n=n*2;
	return 1;
}
int main()
{
	while (GetData())
	{
		printf("%I64d\n",Dijkstra());
	}
	return 0;
}

• Re:Dijkstra可以把这题水过去的 不需要把图显式得表示出来 (0) TheBeet 2007-09-17 00:00:44