1125.c

poj1125用二叉堆优化的Dijkstra算法

#include <stdio.h>
#include <stdlib.h>
#define MAXN 101
#define MAXINT 30000

typedef struct node
{
	int v,w;
	struct node *next;
}node;
typedef struct htype
{
	int v,d,p;
}htype;

node *g[MAXN];
int n,s,hl;
htype heap[MAXN];
int hpos[MAXN];
int anss,ansm;

void insert(int u,int v,int w)
{
	node *p;

	p=(node *)malloc(sizeof(node));
	p->v=v;
	p->w=w;
	p->next=g[u];
	g[u]=p;
}

void init()
{
	int i,j,v,w;

	for (i=0;i<MAXN;i++) g[i]=NULL;
	for (i=1;i<=n;i++)
	{
		scanf("%d",&j);
		while (j)
		{
			j--;
			scanf("%d%d",&v,&w);
			insert(i,v,w);
		}
	}
}

void swap(int a,int b)
{
	heap[0]=heap[a];
	heap[a]=heap[b];
	heap[b]=heap[0];
	hpos[heap[a].v]=a;
	hpos[heap[b].v]=b;
}

void decrease(int i)
{
	while (i>1&&heap[i].d<heap[i>>1].d)
	{
		swap(i,i>>1);
		i=i>>1;
	}
}

void heapfy()
{
	int i;
	
	i=2;
	while (i<=hl)
	{
		if (i<hl&&heap[i+1].d<heap[i].d) i++;
		if (heap[i].d<heap[i>>1].d)
		{
			swap(i,i>>1);
			i*=2;
		}
		else break;
	}
}

void relax(int u,int v,int w)
{
	if (w+heap[hpos[u]].d<heap[hpos[v]].d)
	{
		heap[hpos[v]].d=w+heap[hpos[u]].d;
		heap[hpos[v]].p=u;
		decrease(hpos[v]);
	}
}

void Dijkstra()
{
	int u;
	node *p;

	for (u=1;u<=n;u++)
	{
		heap[u].v=u;
		heap[u].d=MAXINT;
		heap[u].p=0;
		hpos[u]=u;
	}
	heap[s].p=s;
	heap[s].d=0;
	swap(1,s);
	hl=n;
	while (hl)
	{
		u=heap[1].v;
		swap(1,hl);
		hl--;
		heapfy();
		p=g[u];
		while (p)
		{
			if (hpos[p->v]<=hl) relax(u,p->v,p->w);
			p=p->next;
		}
	}
}

void work()
{
	int i,j,x;

	ansm=anss=-1;
	for (i=1;i<=n;i++)
	{
		s=i;
		Dijkstra();
		x=0;
		for (j=1;j<=n;j++) 
		{
			if (i!=j&&(heap[hpos[j]].d>x||x==0)) x=heap[hpos[j]].d;
		}
		if (x==MAXINT||x==0) continue;
		if (ansm==-1||ansm>x)
		{
			anss=i;
			ansm=x;
		}
	}
	if (anss==-1) printf("disjoint\n");
	else printf("%d %d\n",anss,ansm);
}
main()
{
	//freopen("0.txt","r",stdin);
	while (1)
	{
		scanf("%d",&n);
		if (n==0) break;
		init();
		work();
	}
}