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 = [[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^5
routes[i] 中的所有值 互不相同
sum(routes[i].length) <= 10^5
0 <= routes[i][j] < 10^6
0 <= source, target < 10^6

题解

开始看到题面第一想法当然是建图，每个route连完全图，问题就转化为source到target的单源最短距离，使用堆优化的Dijstra算法，可以在内找到最优解；

但是很快就想到不对劲，总点数最大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算法都是可以过的

车站总数为,route总数为n, 建图复杂度为,最短路复杂度为;

源

# 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; // Output: 2

    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; // Output: -1

    return 0;
}

leetcode815

Leetcode 815：公交路线

题目

题解

源