【单源最短路 图论】3112. 访问消失节点的最少时间

本文涉及知识点

单源最短路
图论知识汇总

Leetcode3112. 访问消失节点的最少时间

给你一个二维数组 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 。

提示：
1 <= n <= 5 * 10⁴
0 <= edges.length <= 10⁵
edges[i] == [ui, vi, lengthi]
0 <= ui, vi <= n - 1
1 <= lengthi <= 10⁵
disappear.length == n
1 <= disappear[i] <= 10⁵

单源最短路

不能用朴素单源最短路，时间复杂度O(nn)=O(10⁸)
用堆优化单源路径，时间复杂度O(eloge)=O(10⁵log10⁵)
最封装类上加一个判断条件：如果距离大于等于disappear[i]则忽略。

代码

class CNeiBo
{
public:	
	static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) 
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
			}
		}
		return vNeiBo;
	}	
	static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<std::pair<int, int>>> vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext)
	{
		vector<vector<int>> vNeiBo(rCount * cCount);
		auto Move = [&](int preR, int preC, int r, int c)
		{
			if ((r < 0) || (r >= rCount))
			{
				return;
			}
			if ((c < 0) || (c >= cCount))

			{
				return;
			}
			if (funVilidCur(preR, preC) && funVilidNext(r, c))
			{
				vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c);
			}
		};

		for (int r = 0; r < rCount; r++)
		{
			for (int c = 0; c < cCount; c++)
			{
				Move(r, c, r + 1, c);
				Move(r, c, r - 1, c);
				Move(r, c, r, c + 1);
				Move(r, c, r, c - 1);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Mat(vector<vector<int>>& neiBoMat)
	{
		vector<vector<int>> neiBo(neiBoMat.size());
		for (int i = 0; i < neiBoMat.size(); i++)
		{
			for (int j = i + 1; j < neiBoMat.size(); j++)
			{
				if (neiBoMat[i][j])
				{
					neiBo[i].emplace_back(j);
					neiBo[j].emplace_back(i);
				}
			}
		}
		return neiBo;
	}
};

//堆（优先队列)优化迪杰斯特拉算法 狄克斯特拉(Dijkstra)算法详解
typedef pair<long long, int> PAIRLLI;
class  CMyHeapDis
{
public:
	CMyHeapDis(vector<int>& disappear,int n, long long llEmpty = LLONG_MAX / 10) :m_llEmpty(llEmpty),m_disappear(disappear)
	{
		m_vDis.assign(n, m_llEmpty);
	}
	void Cal(int start, const vector<vector<pair<int, int>>>& vNeiB)
	{
		std::priority_queue<PAIRLLI, vector<PAIRLLI>, greater<PAIRLLI>> minHeap;
		minHeap.emplace(0, start);
		while (minHeap.size())
		{
			const long long llDist = minHeap.top().first;
			const int iCur = minHeap.top().second;
			minHeap.pop();
			if (m_llEmpty != m_vDis[iCur])
			{
				continue;
			}
			if (llDist >= m_disappear[iCur]) {
				continue;
			}
			m_vDis[iCur] = llDist;
			for (const auto& it : vNeiB[iCur])
			{
				minHeap.emplace(llDist + it.second, it.first);
			}
		}
	}
	vector<long long> m_vDis;
	const long long m_llEmpty;
	vector<int>& m_disappear;
};

class Solution {
public:
	vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
		auto neiBo = CNeiBo::Three(n, edges, false);
		CMyHeapDis dis(disappear,n,m_llNotMay);
		dis.Cal(0, neiBo);	
		vector<int> vRet;
		for (int i = 0; i < n; i++) {
			vRet.emplace_back((m_llNotMay==dis.m_vDis[i])?-1: dis.m_vDis[i]);
		}
		return vRet;
	}
	const long long m_llNotMay = 1'000'000'000'000LL;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。