Djkastra堆（手写堆）优化版

Djkastra堆（手写堆）优化版

直接上代码
代码中的注释掉的部分为C++优先队列实现

#include
#include 
#include
#include
#include
#include 
using namespace std;
typedef pair PII; // first 存距离   second 存编号 
const int maxn = 2e5+10;
int n, m; // 村庄数，边数 
int cnt = 0;
int dist[maxn];
bool st[maxn]; // 第 i 个点的最短路是否确定，是否需要更新 
int head[maxn];
struct Edge {
	int to, next, w;
}e[maxn];

// ***** 小根堆 ************************************************************************************************** 
typedef struct node {
	int index;
	int len;
} Pos;

typedef struct HeapStruct {
	Pos *Element; // 存储堆元素的数组
	int Size; // 堆的当前元素个数（最后一个元素的下标）
	int MaxSize; // 堆的存储空间大小 
} HeapStruct, *MinHeap;

// 创建一个大小为MaxSize的堆 
MinHeap Create (int MaxSize) {
	MinHeap H = (MinHeap) malloc (sizeof(struct HeapStruct)); // 分配堆结构空间
	H->Element = (Pos *) malloc ((MaxSize + 1) * sizeof(Pos)); // 分配存储堆元素的数组的空间
	H->Size = 0;
	H->MaxSize = MaxSize; 
	H->Element[0].len = INT_MIN; // 数组的第一个元素放极小元素，数组第二个元素放堆中 

	return H; 
}

// 释放堆申请的空间 
void Destroy(MinHeap H) {
	free(H->Element); // 先释放堆结点的数组空间 
	free(H); // 再释放堆结点的空间 
}

// 判断小根堆是否为空
bool IsEmpty(MinHeap H) {
	return (H->Size == 0);
}

// 判断最小堆是否已满 
bool IsFull(MinHeap H) {
	return (H->Size == H->MaxSize); // 判断最小堆中的元素个数Size是否等于最大容量 
} 

// 将元素 item 插入最小堆 H 
void Insert(MinHeap H, Pos item) {
	int i = 0;
	
	// 判断堆 H 是否已满
	if (IsFull(H)) {
		printf("Heap is fulln");
		return ;
	} 
	
	
	H->Size++;
	for(i = H->Size; H->Element[i / 2].len > item.len; i = i / 2) {
		H->Element[i] = H->Element[i / 2];
	}
	H->Element[i] = item;
}

// 返回最小堆堆顶 
Pos Delete(MinHeap H) {
	int parent = 0, child = 0;
	Pos item, temp;
	
	if (IsEmpty(H)) {
		printf("Heap is Emptyn");
		return H->Element[0];
	}
	
  	item = H->Element[1];
  	temp = H->Element[H->Size];
  	H->Size--;
  	for(parent = 1; parent * 2 <= H->Size; parent = child) {
  		child = parent * 2;
  		// 找出左右结点最小的那个
		if(child != H->Size && (H->Element[child].len > H->Element[child + 1].len)) {
			child++;
		} 
		// 比较它与最小的子节点的大小，如果它比较大，则两者互换位置，否则跳出循环 
		if(temp.len > H->Element[child].len) {
			H->Element[parent] = H->Element[child];
		}
		else break;
	}
	H->Element[parent] = temp;
	return item;
}

// ***** 链式前向星 *********************************************************************************************** 
void add(int u, int v, int w) {
	e[++cnt].next = head[u];
	e[cnt].to = v;
	e[cnt].w = w;
	head[u] = cnt;
}

void init() {
	memset(dist, 0x3f3f3f3f, sizeof(dist)); // 将所有距离初始化为正无穷 
	memset(head, 0, sizeof(head));
	memset(e, 0, sizeof(e));
	cnt = 0;
}

// ***** DJ *************************************************************************************************** 
int dijkstra(int k) {
	dist[k] = 0; // 第一个点到起点的距离
	
//	priority_queue, greater > heap; // 小根堆 
	MinHeap H;
	H = Create(m); 
	
//	heap.push({0,k});
	Insert(H, {k, 0});
	
	while(!IsEmpty(H)) { // 堆不空 
//		PII t = heap.top();
		Pos t = Delete(H);
//		heap.pop();

		int ver = t.index, dis = t.len;
		if(st[ver]) continue; // 重边（访问过的）就不用再更新了，DJ思想就是贪心的访问每条最短边
		st[ver] =  true; // 标记 t 已经确定为最短路
		
		for(int i = head[ver]; i; i = e[i].next) {
			int to = e[i].to;
			if(dist[to] > dis + e[i].w) {
				dist[to] = dis + e[i].w;
//				heap.push({dist[to], to});
				Insert(H, {to, dist[to]});
			}
		}
	}
}

int main() {
	freopen("test3.in", "r", stdin);
	int k, p; // k为起点 p为终点
	while(~scanf("%d%d%d%d", &n, &m, &k, &p)) {
		init();
		for(int i = 1; i <= m; i++) {
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			add(u, v, w);
		}
		dijkstra(k);
		if(dist[p] != 0x3f3f3f3f) {
			printf("%dn", dist[p]); // 到达目标的最短距离。 DJ计算一个起点，多个终点 
		}
		else printf("无法到达！n");
	}
	return 0;
}