【单源最短路 图论】882. 细分图中的可到达节点_图论 细分图

作者推荐

视频算法专题

本文涉及知识点

单源最短路 图论

LeetCode 882. 细分图中的可到达节点

给你一个无向图（原始图），图中有 n 个节点，编号从 0 到 n - 1 。你决定将图中的每条边 细分 为一条节点链，每条边之间的新节点数各不相同。
图用由边组成的二维数组 edges 表示，其中 edges[i] = [ui, vi, cnti] 表示原始图中节点 ui 和 vi 之间存在一条边，cnti 是将边 细分 后的新节点总数。注意，cnti == 0 表示边不可细分。
要 细分 边 [ui, vi] ，需要将其替换为 (cnti + 1) 条新边，和 cnti 个新节点。新节点为 x1, x2, …, xcnti ，新边为 [ui, x1], [x1, x2], [x2, x3], …, [xcnti-1, xcnti], [xcnti, vi] 。
现在得到一个 新的细分图 ，请你计算从节点 0 出发，可以到达多少个节点？如果节点间距离是 maxMoves 或更少，则视为 可以到达 。
给你原始图和 maxMoves ，返回 新的细分图中从节点 0 出发 可到达的节点数 。

示例 1：

输入：edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
输出：13
解释：边的细分情况如上图所示。
可以到达的节点已经用黄色标注出来。
示例 2：

输入：edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4
输出：23
示例 3：

输入：edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]], maxMoves = 17, n = 5
输出：1
解释：节点 0 与图的其余部分没有连通，所以只有节点 0 可以到达。

提示：

0 <= edges.length <= min(n * (n - 1) / 2, 10⁴)
edges[i].length == 3
0 <= ui < vi < n
图中 不存在平行边
0 <= cnti <= 10⁴
0 <= maxMoves <= 10⁹
1 <= n <= 3000

单源最短路

朴素单源最短路的时间复杂度是:O(nn)，本文是就是：O(9e6)，很可能超时。
堆优化单源最短路的时间复杂度:O(边数)，边数不超过10⁴。
节点分两种：原始节点、细分节点。
原始节点到0的距离 <= maxMoves，则能到达。
细分点：枚举各边的两个端点，如果端点能到达，且距离为dis，则通过此端点能够到达 maxMoves - dis 个细分点。
同一条边的两个端点到达的细分点需要去重。

代码

核心代码

//堆（优先队列)优化迪杰斯特拉算法 狄克斯特拉(Dijkstra)算法详解
typedef pair<long long, int> PAIRLLI;
class  CHeapDis
{
public:
	CHeapDis(int n,long long llEmpty = LLONG_MAX/10):m_llEmpty(llEmpty)
	{
		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;
			}
			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;
};

class Solution {
public:
	int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
		vector<vector<pair<int, int>>> vNeiBo(n);
		for (const auto& v : edges) {
			vNeiBo[v[0]].emplace_back(std::make_pair( v[1],v[2]+1 ));
			vNeiBo[v[1]].emplace_back(std::make_pair(v[0], v[2] + 1));
		}
		CHeapDis dis(n);
		dis.Cal(0, vNeiBo);
		int iRet = 0;
		for (int i = 0; i < n; i++) {
			iRet += (dis.m_vDis[i] <= maxMoves);
		}
		for (const auto& v : edges) {
			int i0 = (int)max(0LL, maxMoves - dis.m_vDis[v[0]]);
			int i1 = (int)max(0LL, maxMoves - dis.m_vDis[v[1]]);
			iRet += min(v[2], i0 + i1);
		}
		return iRet;
	}
};
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

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	vector<vector<int>> edges;
	int maxMoves, n;
	{
		edges = { {1,2,4},{1,4,5},{1,3,1},{2,3,4},{3,4,5} }, maxMoves = 17, n = 5;
		auto res = Solution().reachableNodes(edges, maxMoves, n);
		Assert(1, res);
	}
	{
		edges = { {0,1,10},{0,2,1},{1,2,2} }, maxMoves = 6, n = 3;
		auto res = Solution().reachableNodes(edges, maxMoves, n);
		Assert(13, res);
	}
	{
		edges = { {0,1,4},{1,2,6},{0,2,8},{1,3,1} }, maxMoves = 10, n = 4;
		auto res = Solution().reachableNodes(edges, maxMoves, n);
		Assert(23, res);
	}
	
	

	//CConsole::Out(res);
}
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

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。