当前位置：首页 > article >正文

【C++图论并集查找】2492. 两个城市间路径的最小分数|1679

article 2025/1/24 6:00:28

本文涉及知识点

C++图论并集查找（并查集)

LeetCode2492. 两个城市间路径的最小分数

给你一个正整数 n ，表示总共有 n 个城市，城市从 1 到 n 编号。给你一个二维数组 roads ，其中 roads[i] = [ai, bi, distancei] 表示城市 ai 和 bi 之间有一条双向道路，道路距离为 distancei 。城市构成的图不一定是连通的。
两个城市之间一条路径的分数定义为这条路径中道路的最小距离。
城市 1 和城市 n 之间的所有路径的最小分数。
注意：
一条路径指的是两个城市之间的道路序列。
一条路径可以多次包含同一条道路，你也可以沿着路径多次到达城市 1 和城市 n 。
测试数据保证城市 1 和城市n 之间至少有一条路径。
示例 1：
在这里插入图片描述

输入：n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
输出：5
解释：城市 1 到城市 4 的路径中，分数最小的一条为：1 -> 2 -> 4 。这条路径的分数是 min(9,5) = 5 。
不存在分数更小的路径。
示例 2：
在这里插入图片描述

输入：n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]
输出：2
解释：城市 1 到城市 4 分数最小的路径是：1 -> 2 -> 1 -> 3 -> 4 。这条路径的分数是 min(2,2,4,7) = 2 。

提示：
2 <= n <= 10⁵
1 <= roads.length <= 10⁵
roads[i].length == 3
1 <= ai, bi <= n
ai != bi
1 <= distancei <= 10⁴
不会有重复的边。
城市 1 和城市 n 之间至少有一条路径。

排序并集查找（并查集）

本题1和n一定在同一连区域，令本连通区域分数最小的边是a,b。则一定可以经过a,b。
1 $\rightarrow a \rightarrow b \rightarrow 1 \rightarrow 2$

代码

核心代码

class CUnionFind
{
public:
	CUnionFind(int iSize) :m_vNodeToRegion(iSize)
	{
		for (int i = 0; i < iSize; i++)
		{
			m_vNodeToRegion[i] = i;
		}
		m_iConnetRegionCount = iSize;
	}	
	CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size())
	{
		for (int i = 0; i < vNeiBo.size(); i++) {
			for (const auto& n : vNeiBo[i]) {
				Union(i, n);
			}
		}
	}
	int GetConnectRegionIndex(int iNode)
	{
		int& iConnectNO = m_vNodeToRegion[iNode];
		if (iNode == iConnectNO)
		{
			return iNode;
		}
		return iConnectNO = GetConnectRegionIndex(iConnectNO);
	}
	void Union(int iNode1, int iNode2)
	{
		const int iConnectNO1 = GetConnectRegionIndex(iNode1);
		const int iConnectNO2 = GetConnectRegionIndex(iNode2);
		if (iConnectNO1 == iConnectNO2)
		{
			return;
		}
		m_iConnetRegionCount--;
		if (iConnectNO1 > iConnectNO2)
		{
			UnionConnect(iConnectNO1, iConnectNO2);
		}
		else
		{
			UnionConnect(iConnectNO2, iConnectNO1);
		}
	}

	bool IsConnect(int iNode1, int iNode2)
	{
		return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
	}
	int GetConnetRegionCount()const
	{
		return m_iConnetRegionCount;
	}
	vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
	{
		const int iNodeSize = m_vNodeToRegion.size();
		vector<int> vRet(iNodeSize);
		for (int i = 0; i < iNodeSize; i++)
		{
			vRet[GetConnectRegionIndex(i)]++;
		}
		return vRet;
	}
	std::unordered_map<int, vector<int>> GetNodeOfRegion()
	{
		std::unordered_map<int, vector<int>> ret;
		const int iNodeSize = m_vNodeToRegion.size();
		for (int i = 0; i < iNodeSize; i++)
		{
			ret[GetConnectRegionIndex(i)].emplace_back(i);
		}
		return ret;
	}
private:
	void UnionConnect(int iFrom, int iTo)
	{
		m_vNodeToRegion[iFrom] = iTo;
	}
	vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
	int m_iConnetRegionCount;
};

		class Solution {
		public:
			int minScore(int n, vector<vector<int>>& roads) {
				CUnionFind uf(n+1);
				for (int i = 0; i < roads.size(); i++) {
					uf.Union(roads[i][0], roads[i][1]);					
				}		
				int ans = INT_MAX;
				for (const auto& e : roads) {
					if (uf.IsConnect(e[0], 1) || uf.IsConnect(e[1], 1)) {
						ans = min(ans, e[2]);
					}
				}
				return ans;
			}
		};

单元测试

int n;
		vector<vector<int>> roads;
		TEST_METHOD(TestMethod11)
		{
			n = 4, roads = { {1,2,9},{2,3,6},{2,4,5},{1,4,7} };
			auto res = Solution().minScore(n, roads);
			AssertEx(5, res);
		}
		TEST_METHOD(TestMethod12)
		{
			n = 4, roads = { {1,2,2},{1,3,4},{3,4,7} };
			auto res = Solution().minScore(n, roads);
			AssertEx(2, res);
		}	
		TEST_METHOD(TestMethod13)
		{
			n = 4, roads = { {2,3,6},{1,4,7} };
			auto res = Solution().minScore(n, roads);
			AssertEx(7, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功