力扣刷题之3112.访问消失节点的最少时间

题干描述

给你一个二维数组 edges 表示一个 n 个点的无向图，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间有一条需要 lengthi 单位时间通过的无向边。

同时给你一个数组 disappear ，其中 disappear[i] 表示节点 i 从图中消失的时间点，在那一刻及以后，你无法再访问这个节点。

注意，图有可能一开始是不连通的，两个节点之间也可能有多条边。

请你返回数组 answer ，answer[i] 表示从节点 0 到节点 i 需要的 最少 单位时间。如果从节点 0 出发 无法 到达节点 i ，那么 answer[i] 为 -1 。

示例 1：

输入：n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5]

输出：[0,-1,4]

解释：

我们从节点 0 出发，目的是用最少的时间在其他节点消失之前到达它们。

• 对于节点 0 ，我们不需要任何时间，因为它就是我们的起点。
• 对于节点 1 ，我们需要至少 2 单位时间，通过 edges[0] 到达。但当我们到达的时候，它已经消失了，所以我们无法到达它。
• 对于节点 2 ，我们需要至少 4 单位时间，通过 edges[2] 到达。

示例 2：

输入：n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,3,5]

输出：[0,2,3]

解释：

我们从节点 0 出发，目的是用最少的时间在其他节点消失之前到达它们。

• 对于节点 0 ，我们不需要任何时间，因为它就是我们的起点。
• 对于节点 1 ，我们需要至少 2 单位时间，通过 edges[0] 到达。
• 对于节点 2 ，我们需要至少 3 单位时间，通过 edges[0] 和 edges[1] 到达。

示例 3：

输入：n = 2, edges = [[0,1,1]], disappear = [1,1]

输出：[0,-1]

解释：

当我们到达节点 1 的时候，它恰好消失，所以我们无法到达节点 1 。

题干分析

       这道题是一个带有节点消失时间限制的最短路径问题。我们可以使用 Dijkstra 算法来解决这个问题，同时在计算路径时考虑节点的消失时间。

解题逻辑

• 邻接表的创建：我们首先将无向图的边表示为邻接表的形式，便于我们在算法中快速访问每个节点的邻接节点及其边的权重。

• 优先队列的使用：我们使用优先队列来存储当前可以访问的节点及其路径长度，每次从优先队列中取出路径长度最短的节点进行扩展。

• 路径更新和节点消失时间判断：

  • 对于每个取出的节点，检查其当前时间是否已经超过其消失时间，若是则跳过。
  • 遍历当前节点的所有邻接节点，计算从当前节点到邻接节点的新路径长度，并检查新路径长度是否小于邻接节点的消失时间。
  • 如果满足条件，则更新邻接节点的最短路径并将其加入优先队列。

• 结果数组的返回：在算法结束后，结果数组中存储了从起点节点0到其他节点的最短路径长度，如果某个节点不可达，则其值为-1。

 完整代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define  MIN_QUEUE_SIZE 64

//定义元素结构体
typedef struct Element {
	int data[2];
}Element;
//定义比较函数指针类型
typedef bool (*compare)(const void*, const void*);
typedef struct PriorityQueue {
	Element* arr;
	int capacity;
	int queueSize;
	compare lessFunc;
}PriorityQueue;

//创建一个元素
Element* createElement(int x, int y) {
	//动态分配内存
	Element* obj = (Element*)malloc(sizeof(Element));
	obj->data[0] = x;
	obj->data[1] = y;
	return obj;
}

//比较两个元素，当第一个元素大于第二个元素时返回true
static bool less(const void* a, const void* b) {
	Element* e1 = (Element*)a;
	Element* e2 = (Element*)b;
	return e1->data[0] > e2->data[0];
}

//比较两个元素，当第一个元素小于第二个元素时返回true
static bool less(const void* a, const void* b) {
	Element* e1 = (Element*)a;
	Element* e2 = (Element*)b;
	return e1->data[0] < e2->data[0];
}

//交换内存块
static void memswap(void* m1, void* m2, size_t size) {
	unsigned char* a = (unsigned char*)m1;
	unsigned char* b = (unsigned char*)m2;
	while (size--)
	{
		*b ^= *a ^= *b ^= *a;
		a++;
		b++;
	}
}

//交换两个元素
static void swap(Element* arr, int i, int j) {
	memswap(&arr[i], &arr[j], sizeof(Element));
}

//下沉操作，保持堆的性质
static void down(Element* arr, int size, int i, compare cmpFunc) {
	for (int k = 2 * i + 1; k < size; k = 2 * k + 1)
	{
		if (k + 1 < size && cmpFunc(&arr[k], &arr[k + 1])) {
			k++;
		}
		if (cmpFunc(&arr[k], &arr[(k - 1) / 2]))
		{
			break;
		}
		swap(arr, k, (k - 1) / 2);
	}
}
//创建一个优先队列
PriorityQueue* createPriorityQueue(compare cmpFunc) {
	PriorityQueue* obj = (PriorityQueue*)malloc(sizeof(PriorityQueue));
	obj->capacity = MIN_QUEUE_SIZE;
	obj->arr = (Element*)malloc(sizeof(Element) * obj->capacity);
	obj->queueSize = 0;
	obj->lessFunc = cmpFunc;
	return obj;
}
//堆化操作
void heapify(PriorityQueue* obj) {
	for(int i = obj->queueSize / 2 - 1; i >= 0; i--) {
		down(obj->arr, obj->queueSize, i, obj->lessFunc);
	}
}
//入队操作
void enQueue(PriorityQueue* obj, Element* e) {
	//检查队列的容量，若队列已满则扩展容量
	if (obj->queueSize == obj->capacity)
	{
		obj->capacity *= 2;
		Element* mem = (Element*)malloc(sizeof(Element) * obj->capacity);
		memcpy(mem, obj->arr, sizeof(Element) * obj->queueSize);
		free(obj->arr);
		obj->arr = mem;
	}
	memcpy(&obj->arr[obj->queueSize], e, sizeof(Element));
	for (int i = obj->queueSize; i > 0 && obj->lessFunc(&obj->arr[(i - 1) / 2], &obj->arr[i]); i = (i - 1) / 2) {
		swap(obj->arr, i, (i - 1) / 2);
	}
	obj->queueSize++;
}
// 出队操作
Element* deQueue(PriorityQueue* obj) {
	swap(obj->arr, 0, obj->queueSize - 1);
	down(obj->arr, obj->queueSize - 1, 0, obj->lessFunc);
	Element* e = &obj->arr[obj->queueSize - 1];
	obj->queueSize--;
	return e;
}

// 判断队列是否为空
bool isEmpty(const PriorityQueue* obj) {
	return obj->queueSize == 0;
}

// 获取队列的队首元素
Element* front(const PriorityQueue* obj) {
	if (obj->queueSize == 0) {
		return NULL;
	}
	else {
		return &obj->arr[0];
	}
}

// 清空队列
void clear(PriorityQueue* obj) {
	obj->queueSize = 0;
}

// 获取队列的大小
int size(const PriorityQueue* obj) {
	return obj->queueSize;
}

// 释放优先队列
void freeQueue(PriorityQueue* obj) {
	free(obj->arr);
	free(obj);
}

// 定义边的结构体
typedef struct Edge {
	int node;
	int length;
	struct Edge* next;
} Edge;

// 创建一个边
Edge* createEdge(int node, int length) {
	Edge* obj = (Edge*)malloc(sizeof(Edge));
	obj->node = node;
	obj->length = length;
	obj->next = NULL;
	return obj;
}

// 释放边链表
void freeList(Edge* list) {
	while (list) {
		Edge* p = list;
		list = list->next;
		free(p);
	}
}
//计算最短时间的函数
int* minimumTime(int n, int** edges, int edgesSize, int* edgesColSize, int* disappear, int disappearSize, int* returnSize) {
	//创建邻接表，用于存储图的结构
	Edge** adj = (Edge**)malloc(sizeof(Edge*) * n);
	for (int i = 0; i < n; i++)
	{
		adj[i] = NULL;//初始化邻接表
	}
	for (int i = 0; i < edgesSize; i++)
	{
		int u = edges[i][0], v = edges[i][1], length = edges[i][2];
		//为节点u添加一个到节点v的边
		Edge* ev = createEdge(v, length);
		ev->next = adj[u];
		adj[u] = ev;
		//为节点v添加一个到节点u的边
		Edge* eu = createEdge(u, length);
		eu->next = adj[v];
		adj[v] = eu;

	}
	//创建优先队列，使用less函数作为比较函数
	PriorityQueue* pq = createPriorityQueue(less);
	Element e;
	e.data[0] = 0;//初始时间为0
	e.data[1] = 0;//起点节点为0
	enQueue(pq, &e);//将起点节点入队
	int* answer = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++)
	{
		answer[i] = -1;
	}
	answer[0] = 0;//起点节点的最短时间为0
	//使用优先队列进行Dijkstra算法
	// 使用优先队列进行Dijkstra算法
	while (!isEmpty(pq)) {
		Element* p = front(pq); // 取出优先队列的队首元素
		int t = p->data[0]; // 当前节点的时间
		int u = p->data[1]; // 当前节点的编号
		deQueue(pq); // 将队首元素出队
		if (t != answer[u]) {
			continue; // 如果当前节点的时间不是最短时间，跳过
		}
		// 遍历当前节点的所有邻接节点
		for (struct Edge* p = adj[u]; p; p = p->next) {
			int v = p->node, length = p->length;
			// 如果从当前节点到邻接节点的时间小于邻接节点的消失时间
			// 且从当前节点到邻接节点的时间小于已知的最短时间
			if (t + length < disappear[v] && (answer[v] == -1 || t + length < answer[v])) {
				e.data[0] = t + length; // 更新邻接节点的时间
				e.data[1] = v; // 更新邻接节点的编号
				enQueue(pq, &e); // 将邻接节点入队
				answer[v] = t + length; // 更新邻接节点的最短时间
			}
		}
	}
	*returnSize = n; // 设置返回结果的大小
	freeQueue(pq); // 释放优先队列
	free(adj); // 释放邻接表内存
	return answer; // 返回最短时间数组
}
// 主函数用于测试
int main() {
	int n = 4; // 节点数量
	int edgesSize = 4; // 边的数量
	int edgesColSize[4] = { 3, 3, 3, 3 }; // 每条边的列数
	int* edges[4]; // 边的数组
	int edge1[] = { 0, 1, 1 }; // 边 0 -> 1, 长度为 1
	int edge2[] = { 0, 2, 4 }; // 边 0 -> 2, 长度为 4
	int edge3[] = { 1, 2, 2 }; // 边 1 -> 2, 长度为 2
	int edge4[] = { 2, 3, 1 }; // 边 2 -> 3, 长度为 1
	edges[0] = edge1;
	edges[1] = edge2;
	edges[2] = edge3;
	edges[3] = edge4;
	int disappear[] = { 100, 100, 100, 100 }; // 节点的消失时间
	int returnSize;
	int* result = minimumTime(n, edges, edgesSize, edgesColSize, disappear, 4, &returnSize);
	for (int i = 0; i < returnSize; i++) {
		printf("%d ", result[i]); // 打印最短时间
	}
	printf("\n");
	free(result); // 释放结果数组
	return 0;
}