dijkstra_heap.cpp

Dijkstra算法

/*
算法：Dijkstra + Heap
适用：时间要求效率高的场合
*/
#include <stdio.h>
#include <string.h>

const int Max = 50010;

struct EDGE
{
	int adj, p;
	int next;
};
EDGE edge[Max*2];
int nedge, head[Max];

int weight[Max];
int n, m;

struct NOD
{
	int id;
	__int64 dis;
};
NOD heap[Max];
int nheap, pid[Max];
char flag[Max];

void insert(int a,int b,int p)
{
	edge[nedge].adj = b;
	edge[nedge].p = p;
	edge[nedge].next = head[a];
	head[a] = nedge ++;
}

void input()
{
	scanf("%d%d",&n,&m);
	int i;
	for(i = 0;i < n;i ++)
		scanf("%d",&weight[i]);
	memset(head,-1,n*sizeof(int));
	nedge = 0;
	for(i = 0;i < m;i ++)
	{
		int a, b, p;
		scanf("%d%d%d",&a,&b,&p);
		a --; b --;
		insert(a, b, p);
		insert(b, a, p);
	}
}

void swap(int i,int j)
{
	NOD tmp = heap[i];
	heap[i] = heap[j];
	heap[j] = tmp;
	pid[heap[i].id] = i;
	pid[heap[j].id] = j;
}

void fixdown(int i)
{
	while(i*2+1 < nheap)
	{
		int j = i*2+1;
		if(j + 1 < nheap&&heap[j+1].dis < heap[j].dis) j ++;
		if(heap[i].dis < heap[j].dis) break;
		swap(i,j);
		i = j;
	}
}

void fixup(int i)
{
	while(i > 0)
	{
		int j = (i-1)/2;
		if(heap[i].dis > heap[j].dis) break;
		swap(i,j);
		i = j;
	}
}

void solve()
{
	memset(pid,-1,n*sizeof(int));
	memset(flag,0,sizeof(flag));
	nheap = 1;
	heap[0].dis = 0; heap[0].id = 0;
	pid[0] = 0;
	__int64 ans = 0;
	for(int i = 0;i < n;i ++)
	{
		if(nheap == 0) { printf("No Answer\n"); return ; }
		__int64 min = heap[0].dis;
		int id = heap[0].id;
		ans += min * weight[id];
		flag[id] = 1;
		swap(0,-- nheap);
		fixdown(0);
		for(int j = head[id];j != -1;j = edge[j].next)
		{
			int v = edge[j].adj;
			int dis = edge[j].p;
			if(flag[v]) continue;
			if(pid[v] == -1)
			{
				heap[nheap].dis = min + dis;
				heap[nheap].id = v;
				pid[v] = nheap ++;
				fixup(nheap - 1);
			}
			else if(min + dis < heap[pid[v]].dis)
			{
				heap[pid[v]].dis = min + dis;
				fixup(pid[v]);
			}
		}
	}
	printf("%I64d\n",ans);
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t --)
	{
		input();
		solve();
	}
	return 0;
}