bool cmp(const Edge & a, const Edge & b)
{
	return a.wt > b.wt;
}


void Insert(int a, int b, int c)
{
	Node * p, * q;
	p = map[a];
	q = new Node;
	q->adjvex=b;
	q->wt=c;
	q->next=p;
	map[a]=q;

	p = map[b];
	q = new Node;
	q->adjvex=a;
	q->wt=c;
	q->next=p;
	map[b]=q;
}


void Dijkstra()
{
	int u;
	Node * p;
	memset(dist,-1,sizeof(dist));
	memset(vis,0,sizeof(vis));
	for (Len=0,p=map[0]; p; p=p->next)
	{
		dist[p->adjvex]=p->wt;
		heap[Len].adj=p->adjvex;
		heap[Len++].wt=p->wt;
	}
	make_heap(heap,heap+Len,cmp);
	dist[0]=0;
	vis[0]=1;
	for (; Len;)
	{
		for (; Len && vis[heap[0].adj]; )pop_heap(heap,heap+Len--,cmp);
		if (Len == 0)
		{
			break;
		}
		u=heap[0].adj;
		vis[u]=1;
		pop_heap(heap,heap+Len--,cmp);
		for (p=map[u]; p; p=p->next)
		{
			if ( ! vis[p->adjvex] && (dist[p->adjvex] < 0 || dist[p->adjvex] > dist[u]+p->wt))
			{
				dist[p->adjvex]=dist[u]+p->wt;
				heap[Len].adj=p->adjvex;
				heap[Len++].wt=dist[p->adjvex];
				push_heap(heap,heap+Len,cmp);
			}
		}
	}
}

• Re:怎么没人，为什么我这样写的heap会挂掉，而用priority_queue写的可以A呢，我heap开了5000000大 (1181) ACM06019 2006-10-27 22:06:09
• 我也是这么写的，也错了 (11) bmexue 2006-12-20 23:55:08