题目描述

文字版

代码

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>> g;
        // 因为答案求最小 距离初期化最大
        // 公交车数量为联通点
        vector<int> dist(n, 1e8);
        queue<int> q;
        // 公交车数量为联通点
        for (int i = 0; i < n; i ++ ) {
            for (int x: routes[i]) {
                if (x == source) {
                    // 初期化联通点 距离是1
                    dist[i] = 1;
                    // 初期化联通点 加入队列
                    q.push(i);
                }
                // 当前车站属于联通点
                g[x].push_back(i);
            }
        }
        // 枚举联通点
        // bfs求最短路
        while (q.size()) {
            int t = q.front();
            q.pop();

            // 枚举联通点下的车站
            for (auto x: routes[t]) {
                // 找到车站 返回联通点距离
                if (x == target) return dist[t];
                // 枚举车站下的联通点
                // 找到最短的能到达的联通点
                for (auto y: g[x]) {
                    // 如果没有遍历过
                    if (dist[y] > dist[t] + 1) {
                        // 更新距离
                        dist[y] = dist[t] + 1;
                        q.push(y);
                    }
                }
                // 枚举过的车站 删除
                g.erase(x);
            }
        }
        return -1;
    }
};