Leetcode 815：公交路线
给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
- 例如，路线
routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
示例 1：
1
2
3
| 输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
|
示例 2：
1
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^5routes[i] 中的所有值 互不相同sum(routes[i].length) <= 10^50 <= routes[i][j] < 10^60 <= source, target < 10^6
题解
开始看到题面第一想法当然是建图，每个route连完全图， 问题就转化为source到target的单源最短距离，使用堆优化的Dijstra算法，可以在$O((|V|+|E|)log|V|)$内找到最优解；
但是很快就想到不对劲，总点数最大10w，当点数很大而且接近稠密图时复杂度基本会爆炸，但是有一个特例，当点数很多但是只有两三个route时，直觉上遍历几遍就出来了（因为route内部是完全图），这个复杂度不符合我们的预期；
此时我已经放弃单源最短路径，已经转而想其他的搜索算法了，最终无果；
本质上还是疏于训练的原因，之前在tarjan算法中，我们对于强联通分量直接做缩点，这里也是一样，因为bus可以在route内无代价移动，我们将每个route内完全图缩成一个点，保留缩点以外的边，只需要找到source和target可能在的route中最短距离；
为此我们对每个站点site：int，维护一个R：unordered_map<int, vector<int>> ,记录站点site在哪些完全图route里，优化建图，对每个route(这样的route最多500个)，使用Dijstra算法（甚至不用优化），维护一个队列，对可能的三角形松弛，最后比较可能的答案返回；
甚至优化建图后求全局最短路径使用Floyd算法都是可以过的
车站总数为$N$,route总数为n, 建图复杂度为$O(Nn)$,最短路复杂度为$O(n^2)$;
源
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
| # include <vector>
# include <iostream>
# include <unordered_map>
# include <climits>
# include <queue>
using namespace std;
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
if(source == target) return 0;
int n = routes.size();
unordered_map<int, vector<int>> R;
vector<vector<int>> edge(n, vector<int>(n));
for(int i = 0; i < n; i++){
for(int site : routes[i]){
for(int j: R[site]){
edge[j][i]=edge[i][j]=1;
}
R[site].push_back(i);
}
}
queue<int> q;
vector<int> dis(n, -1);
for(int direct: R[source]){
dis[direct] = 1;
q.push(direct);
}
while(!q.empty()){
int u = q.front();
q.pop();
for(int v = 0; v < n; v++){
if(edge[u][v] && dis[v] == -1){
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
int ans = INT_MAX;
for(int t: R[target]){
if(dis[t]!= -1){
ans = min(ans, dis[t]);
}
}
return ans == INT_MAX? -1 : ans;
}
};
int main(){
vector<vector<int>> routes1 = {{1,2,7},{3,6,7}};
int source1 = 1;
int target1 = 6;
cout << Solution().numBusesToDestination(routes1, source1, target1) << endl;
vector<vector<int>> routes2 = {{7,12},{4,5,15},{6},{15,19},{9,12,13}};
int source2 = 15;
int target2 = 12;
cout << Solution().numBusesToDestination(routes2, source2, target2) << endl;
return 0;
}
|