题目描述

我们有一系列公交路线。每一条路线 routes[i] 上都有一辆公交车在上面循环行驶。例如，有一条路线 routes[0] = [1, 5, 7]，表示第一辆 (下标为 0) 公交车会一直按照 1->5->7->1->5->7->1->… 的车站路线行驶。

假设我们从 S 车站开始（初始时不在公交车上），要去往 T 站。 期间仅可乘坐公交车，求出最少乘坐的公交车数量。返回 -1 表示不可能到达终点车站。

样例

输入: 
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
输出: 2
解释: 
最优策略是先乘坐第一辆公交车到达车站 7, 然后换乘第二辆公交车到车站 6。

注意

• 1 <= routes.length <= 500
• 1 <= routes[i].length <= 500
• 0 <= routes[i][j] < 10 ^ 6

算法1

(宽度优先搜索) $O(n^2 \sum_i^n r_i)$

1. 我们以站 + 公交车号为状态，用哈希表预处理出每个站能坐的公交车号。
2. 初始时我们处于状态 (S, -1)，然后开始进行宽度有限搜索，用 map 记录距离。
3. 直接暴力搜索会导致超时，这里有一个小优化，每个公交车最多只会坐一次，所以再开一个布尔数组记录都坐过的公交车。

时间复杂度

• 假设 $n$ 表示公交车的种类，$r_i$ 表示第 $i$ 个公交车能到的站的数量。
• 预处理需要 $\sum_i^n r_i$ 的时间，搜索时，我们的总状态数是 $O(n \sum_i^n r_i)$，转移首先需要枚举能换乘到哪些公交车，由于我们用布尔数组记录了坐过的公交车，所以均摊的转移复杂度也不会超过 $O(n)$。
• 所以总时间复杂度为 $O(n^2 \sum_i^n r_i)$。

空间复杂度

• 哈希表需要 $O(\sum_i^n r_i)$ 的空间，队列需要 $O(n \sum_i^n r_i)$ 的空间，布尔数组需要 $O(n)$ 的空间，如总空间复杂度为 $O(n \sum_i^n r_i)$。

C++ 代码

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
        unordered_map<int, vector<int>> hash;
        for (int i = 0; i < routes.size(); i++)
            for (auto stop : routes[i]) {
                if (hash.find(stop) == hash.end()) {
                    hash[stop] = {};
                }
                hash[stop].push_back(i);
            }

        if (hash.find(T) == hash.end())
            return -1;

        queue<pair<int, int>> q;
        q.push(make_pair(S, -1));

        unordered_map<string, int> dis;
        dis[to_string(S) + " " + to_string(-1)] = 0;
        vector<bool> vis(routes.size(), false);

        while (!q.empty()) {
            auto u = q.front();
            auto su = to_string(u.first) + " " + to_string(u.second);
            q.pop();
            if (u.first == T)
                return dis[su];
            for (auto bus : hash[u.first])
                if (!vis[bus]) {
                    vis[bus] = true;
                    for (auto stop : routes[bus]) {
                        auto v = make_pair(stop, bus);
                        auto sv = to_string(v.first) + " " + to_string(v.second);
                        if (dis.find(sv) == dis.end()) {
                            dis[sv] = dis[su] + 1;
                            q.push(v);
                        }
                    }
                }
        }
        return -1;
    }
};

算法2

(宽度优先搜索) $O(n^2 \max(r_i))$

1. 由算法 1 启发，我们发现只需要以公交车号作为状态就可以了。
2. 我们需要预处理出哪两个公交车之间可以换乘，暴力枚举。
3. 然后从起点能到的公交车开始，不断进行换乘，然后看是否能到达终点。
4. 这里需要特判起点和终点相同的情况。

时间复杂度

• 预处理暴力枚举需要 $O(n^2 \max(r_i))$ 的复杂度，宽搜状态数为 $O(n)$，每次转移 $O(n)$ 找能换乘到的公交车，宽搜时间复杂度为 $O(n^2)$。
• 所以总时间复杂度为 $O(n^2 \max(r_i))$。

空间复杂度

• 换乘的预处理数组需要 $O(n^2)$ 的空间，队列只需要 $O(n)$ 的空间，故总空间复杂度为 $O(n^2)$。

C++ 代码

class Solution {
public:

    bool check(const vector<int> &x, const vector<int> &y) {
        int i = 0, j = 0;
        while (i < x.size() && j < y.size()) {
            if (x[i] == y[j])
                return true;
            else if (x[i] < y[j])
                i++;
            else
                j++;
        }
        return false;
    }

    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
        if (S == T)
            return 0;

        int n = routes.size();
        vector<vector<int>> trans(n);

        for (int i = 0; i < n; i++)
            sort(routes[i].begin(), routes[i].end());

        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (check(routes[i], routes[j])) {
                    trans[i].push_back(j);
                    trans[j].push_back(i);
                }

        vector<int> dis(routes.size(), INT_MAX);
        queue<int> q;
        for (int i = 0; i < routes.size(); i++)
            for (auto stop : routes[i])
                if (stop == S) {
                    q.push(i);
                    dis[i] = 1;
                    break;
                }

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (auto stop : routes[u])
                if (stop == T)
                    return dis[u];

            for (auto v : trans[u])
                if (dis[v] > dis[u] + 1) {
                    dis[v] = dis[u] + 1;
                    q.push(v);
                }
        }
        return -1;
    }
};