本文涉及知识点

C++图论
C++BFS算法

LeetCode815. 公交路线

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> … 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
示例 1：
输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
示例 2：
输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1
提示：
1 <= routes.length <= 500.
1 <= routes[i].length <= 10⁵
routes[i] 中的所有值 互不相同
sum(routes[i].length) <= 10⁵
0 <= routes[i][j] < 10⁶
0 <= source, target < 10⁶

BFS

每个公交站是一节点，每辆公交看做一个虚拟节点。公交站的编号是原始编号，公交的编号=10⁶+原始编号。
包括虚拟节点,x个节点可以到达。则虚拟节点共有x/2个。路线必定是节点或虚拟节点交替出现。
如果x是-1,直接返回。别除以2。
时间复杂度：O(n+m) n是公交的数量,m = sum(routes[i].length)
如果直接节点两两相连，时间复杂度：O(mm)。

代码

核心代码

class Solution {
		public:
			int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
				unordered_map<int, vector<int>> neiBo;
				for (int i = 0; i < routes.size(); i++) {
					const int iVri = 1'000'000 + i;
					for (const auto& j : routes[i])
					{
						neiBo[iVri].emplace_back(j);
						neiBo[j].emplace_back(iVri);
					}
				}
				unordered_map<int, int> dis;
				queue<int> que;
				auto Add = [&](int cur,int iDis) {
					if (dis.count(cur)) { return; }
					dis[cur] = iDis;
					que.emplace(cur);
				};
				Add(source, 0);
				while (que.size()) {
					const auto cur = que.front();
					que.pop();
					for (const auto& next : neiBo[cur]) {
						Add(next, dis[cur] + 1);
					}
				}
				return dis.count(target) ? (dis[target] / 2) : -1;
			}
		};

核心代码

	vector<vector<int>> routes;
		int source,  target;
		TEST_METHOD(TestMethod11)
		{
			routes = { {1,2,7},{3,6,7} }, source = 1, target = 6;
			auto res = Solution().numBusesToDestination(routes,source,target);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			routes = { {7,12},{4,5,15},{6},{15,19},{9,12,13} }, source = 15, target = 12;
			auto res = Solution().numBusesToDestination(routes, source, target);
			AssertEx(-1, res);
		}