题目描述
这是 LeetCode 上的 815. 公交路线 ,难度为 困难。
给你一个数组 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 = , source = 15, target = 12
输出:-1
|
提示:
- 1 <= routes.length <= 500.
- 1 <= routes[i].length <= $10^5$
- routes[i] 中的所有值 互不相同
- sum(routes[i].length) <= $10^5$
- 0 <= routes[i][j] < $10^6$
- 0 <= source, target < $10^6$
基本分析
为了方便,我们令每个公交站为一个「车站」,由一个「车站」可以进入一条或多条「路线」。
问题为从「起点车站」到「终点车站」,所进入的最少路线为多少。
抽象每个「路线」为一个点,当不同「路线」之间存在「公共车站」则为其增加一条边权为 $1$ 的无向边。
单向 BFS
由于是在边权为 $1$ 的图上求最短路,我们直接使用 BFS
即可。
起始时将「起点车站」所能进入的「路线」进行入队,每次从队列中取出「路线」时,查看该路线是否包含「终点车站」:
- 包含「终点车站」:返回进入该线路所花费的距离
- 不包含「终点车站」:遍历该路线所包含的车站,将由这些车站所能进入的路线,进行入队
一些细节:由于是求最短路,同一路线重复入队是没有意义的,因此将新路线入队前需要先判断是否曾经入队。

代码:
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
| class Solution { int s, t; int[][] rs; public int numBusesToDestination(int[][] _rs, int _s, int _t) { rs = _rs; s = _s; t = _t; if (s == t) return 0; int ans = bfs(); return ans; } int bfs() { Map<Integer, Set<Integer>> map = new HashMap<>(); Deque<Integer> d = new ArrayDeque<>(); Map<Integer, Integer> m = new HashMap<>(); int n = rs.length; for (int i = 0; i < n; i++) { for (int station : rs[i]) { if (station == s) { d.addLast(i); m.put(i, 1); } Set<Integer> set = map.getOrDefault(station, new HashSet<>()); set.add(i); map.put(station, set); } } while (!d.isEmpty()) { int poll = d.pollFirst(); int step = m.get(poll);
for (int station : rs[poll]) { if (station == t) return step;
Set<Integer> lines = map.get(station); if (lines == null) continue; for (int nr : lines) { if (!m.containsKey(nr)) { m.put(nr, step + 1); d.add(nr); } } } } return -1; } }
|
- 时间复杂度:令路线的数量为 $n$,车站的数量为 $m$。建图的时间复杂度为 $O(\sum{i=0}^{n-1} len(rs[i]))$;
BFS
部分每个路线只会入队一次,最坏情况下每个路线都包含所有车站,复杂度为 $O(n m)$。整体复杂度为 $O(n m + \sum{i=0}^{n-1} len(rs[i]))$。
- 空间复杂度:$O(n * m)$
双向 BFS(并查集预处理无解情况)
另外一个做法是使用双向 BFS
。
首先建图方式不变,将「起点」和「终点」所能进入的路线分别放入两个方向的队列,如果「遇到公共的路线」或者「当前路线包含了目标位置」,说明找到了最短路径。
另外我们知道,双向 BFS
在无解的情况下不如单向 BFS
。因此我们可以先使用「并查集」进行预处理,判断「起点」和「终点」是否连通,如果不联通,直接返回 $-1$,有解才调用双向 BFS
。
由于使用「并查集」预处理的复杂度与建图是近似的,增加这样的预处理并不会越过我们时空复杂度的上限,因此这样的预处理是有益的。一定程度上可以最大化双向 BFS
减少搜索空间的效益。

代码:
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
| class Solution { static int N = (int)1e6+10; static int[] p = new int[N]; int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; } void union(int a, int b) { p[find(a)] = p[find(b)]; } boolean query(int a, int b) { return find(a) == find(b); } int s, t; int[][] rs; public int numBusesToDestination(int[][] _rs, int _s, int _t) { rs = _rs; s = _s; t = _t; if (s == t) return 0; for (int i = 0; i < N; i++) p[i] = i; for (int[] r : rs) { for (int loc : r) { union(loc, r[0]); } } if (!query(s, t)) return -1; int ans = bfs(); return ans; } Map<Integer, Set<Integer>> map = new HashMap<>(); int bfs() { Deque<Integer> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>(); Map<Integer, Integer> m1 = new HashMap<>(), m2 = new HashMap<>(); int n = rs.length; for (int i = 0; i < n; i++) { for (int station : rs[i]) { if (station == s) { d1.addLast(i); m1.put(i, 1); } if (station == t) { d2.addLast(i); m2.put(i, 1); } Set<Integer> set = map.getOrDefault(station, new HashSet<>()); set.add(i); map.put(station, set); } }
Set<Integer> s1 = map.get(s), s2 = map.get(t); Set<Integer> tot = new HashSet<>(); tot.addAll(s1); tot.retainAll(s2); if (!tot.isEmpty()) return 1;
while (!d1.isEmpty() && !d2.isEmpty()) { int res = -1; if (d1.size() <= d2.size()) { res = update(d1, m1, m2); } else { res = update(d2, m2, m1); } if (res != -1) return res; }
return 0x3f3f3f3f; } int update(Deque<Integer> d, Map<Integer, Integer> cur, Map<Integer, Integer> other) { int m = d.size(); while (m-- > 0) { int poll = d.pollFirst(); int step = cur.get(poll);
for (int station : rs[poll]) { Set<Integer> lines = map.get(station); if (lines == null) continue; for (int nr : lines) { if (cur.containsKey(nr)) continue; if (other.containsKey(nr)) return step + other.get(nr); cur.put(nr, step + 1); d.add(nr); } } } return -1; } }
|
- 时间复杂度:令路线的数量为 $n$,车站的个数为 $m$。并查集和建图的时间复杂度为 $O(\sum{i=0}^{n-1} len(rs[i]))$;
BFS
求最短路径的复杂度为 $O(n m)$。整体复杂度为 $O(n m + \sum{i=0}^{n-1} len(rs[i]))$。
- 空间复杂度:$O(n * m + \sum_{i=0}^{n-1} len(rs[i]))$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.815
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。