LeetCode.815 公交路线

题目

难度:困难

我们有一系列公交路线。每一条路线 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.

思路

广度优先搜索,最短路径

把每一辆车看成图中的一个顶点,除此外,S和T站点也当成图中的顶点看。
这样,我们可以构建一个包含所有车和S、T的图,它的边表示两辆车的路线有交集,或表示某辆车的路线与S或T有交集。
这样问题变成了求图中S和T的最短路径。

代码

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

        int N = routes.size();
        vector<vector<int>> graph(N);
        set<int> seen;      // 标识i是否被加入过q队列
        set<int> targets;   // 经过T站点的公交车
        queue<std::pair<int, int>> q;   // 用于BFS的辅助队列

        // 构建graph
        for (int i = 0; i < N; ++ i) {
            for (int j = 0; j < N; ++ j) {
                if (vector_intersection(routes[i], routes[j])) {
                    graph[i].push_back(j);
                    graph[j].push_back(i);
                }
            }
        }

        for (int i = 0; i < N; ++ i) {
            if (std::find(routes[i].begin(), routes[i].end(), S) != routes[i].end()) {  // 公交车i会经过S站点
                seen.insert(i);
                q.push(std::make_pair(i, 0));
            }
            if (std::find(routes[i].begin(), routes[i].end(), T) != routes[i].end()) {  // 公交车i会经过T站点
                targets.insert(i);
            }
        }

        while (!q.empty()) {
            int bus = q.front().first;
            int depth = q.front().second;
            q.pop();

            if (targets.count(bus))
                return depth + 1;

            for (auto nei : graph[bus]) {
                if (!seen.count(nei)) {
                    seen.insert(nei);
                    q.push(std::make_pair(nei, depth + 1));
                }
            }
        }

        return -1;
    }

    static bool vector_intersection(const vector<int>& v1, const vector<int>& v2) {
        vector<int> v;
        set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(v));
        return !v.empty();
    }
};
喜欢()
评论 (0)