LeetCode 815. 公交路线

摘要：
一道较为抽象的BFS最短路问题。

题目

给你一个数组 $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$

---

BFS

图片作者：div@acwing

可以将每个路线抽象成一个点，题目即求出从某个路线到目标路线的最短距离。

建图（以路线抽象成的点构成的图）：将每个点对应的路线存到哈希表中，如果遍历到的某个点存在着除自己所在路线外的其他路线，那么就可以从当前路线BFS到另外这条路线上。

我们维护一个距离数组记录距离，亦可作为标记数组。

• C++

/*
 * 2021-6-28 23:21:19
 * author: etoa
 */
static const auto shutdown = [](){
    cin.tie(nullptr)->sync_with_stdio(false);
    return nullptr;
}();

class Solution {
public:
    static constexpr int N = 510;
    int q[N];                                       // 路线队列
    int hh = 0, tt = -1;

    unordered_map<int, vector<int>> hash;           // 点对应相关的所有路线

    int dist[N];                                    // 路线对应已走过的距离，同时具备标记已走过的路线的功能（初始化成无穷大，如果值不是无穷大说明已经走过）

    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if (source == target) return 0;
        int len = routes.size();
        memset(dist, 0x3f, sizeof dist);

        for (int i = 0; i < len; i++) {             // 遍历所有路线找到起点
            for (auto &x : routes[i]) {
                if (x == source) {                  // 找到起始点
                    q[++tt] = i;                    // 将对应路线入队
                    dist[i] = 1;                    // 至少需要一站路，距离从1开始，将来BFS到其他路线，距离增加1
                }
                hash[x].push_back(i);               //将所有点和其所在的路线对应起来
            }
        }

        for (; tt >= hh;) {
            int cur = q[hh++];
            for (auto &x : routes[cur]) {
                if (x == target) return dist[cur];  // 找到目标点，返回距离
                                                    // 否则将点对应的所有路线入队，注意跳过已走过的路线，因为已走过的路线及上面所有点必然已经被遍历过一次，点对应的所有路线必然已被入队，避免重复
                for (auto &i : hash[x]) {
                    if (dist[i] == 0x3f3f3f3f) {    // 新的路线
                        q[++tt] = i;                // 路线入队
                        dist[i] = dist[cur] + 1;    // 将下一个路线距离在本路线基础上+1，顺便标记为已访问
                    }
                                                    // 否则是已访问过的路线（已入队或已遍历），直接跳过
                }
                                                    // 将已遍历过的点擦除，道理和标记已访问过的路线一样，只要点被遍历过，那么它对应的所有路线必然已入队。
                hash.erase(x);                      // 将已遍历的点从hashmap中删除，为什么不从别的地方删除？
            }
        }
        return -1;
    }
};

原题链接： LeetCode 815. 公交路线