标签搜索

目 录CONTENT

文章目录

公交路线.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 4 阅读 / 2,877 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

公交路线

@[toc]

一、问题描述

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

方法一:

  • Graph用来存储线路与线路是否有交集,node为各个线路,若有交集则建立一条无向边。
  • 建好图后用广度优先遍历,求最短路径
//#include <algorithm>

class Solution {
public:
    bool isIntersected(vector<int>& route1, vector<int>& route2) {
        int i = 0, j = 0;
        while(i < route1.size() && j < route2.size()) {
            if (route1[i] == route2[j]) return true;
            if (route1[i] > route2[j]) {
                ++j;
            } else {
                ++i;
            }
        }
        return false;
    }

    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
        if (S == T) return 0;
        // S和T也单独作为一条线路
        routes.push_back({S});
        routes.push_back({T});
        
        // Graph用来存储线路与线路是否有交集,node为各个线路,若有交集则建立一条无向边
        vector<vector<int>> graph(routes.size());
        // 初始化Graph
        // 1. 排序:是为了用双指针判断是否相交
        // 2. 判断是否有交集,有交集则可到达,在Graph中增加一条边(在二维vector中增加两个线路index的对应关系)
        for (auto route : routes) {
            sort(route.begin(), route.end());
        }
        for (int i = 0; i < routes.size(); ++i) {
            for (int j = i; j < routes.size(); ++j) {
                if (isIntersected(routes[i], routes[j])) {
                    // 无向图,所以两个方向都可达
                    graph[i].push_back(j);
                    graph[j].push_back(i);
                }
            }
        }

        // S和T是最后加入到routes里的,下标分别为倒数第二个和倒数第一个
        int t_index = routes.size() - 1;
        int s_index = t_index - 1;

        // 根据Graph的对应关系,广度优先遍历,节点加入queue
        // 每个点的最短路径存放在dist[n]
        // 每次取出后,若之前已有更短路径(dist[i]已更新,不为默认值-1),则跳过;若未到达,则更新到此点的最短路径
        queue<int> q;
        q.push(s_index);

        vector<int> dist(routes.size(), -1);
        dist[s_index] = 0;  // 求出dist[t_index]后返回

        while (!q.empty()) {
            int route_index = q.front();
            q.pop();
            // t_index对应的线路为最后加入的,并不存在此线路;到达此线路说明上一个线路包含站点T
            if (route_index == t_index) return dist[t_index] - 1;
            for (int route : graph[route_index]) {
                if (dist[route] == -1) {
                    dist[route] = dist[route_index] + 1;
                    q.push(route);
                }
            }
        }
        
        return -1;
    }
};

方法二:

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
        if (S == T) return 0;
        int N = routes.size();
        map<int, set<int> > m; // 存储车站能通到哪些路线
        for (int i = 0; i < N; ++i) {
            for (auto j : routes[i]) {
                m[j].insert(i);
            }
        }
        vector<bool> visited(N, false); // 哪些路线被遍历过了
        queue<int> q; // 存储已经遍历过的路线
        for (auto x : m[S]) {
            q.push(x);
            visited[x] = true;
        }
        int step = 0;
        while (!q.empty()) {
            ++step;
            int s = q.size();
            for (int i = 0; i < s; ++i) {
                int t = q.front();
                q.pop();
                for (auto j : routes[t]) {
                    if (j == T) return step;
                    for (auto x : m[j]) {
                        if (!visited[x]) {
                            q.push(x);
                            visited[x] = true;
                        }
                    }
                }
            }
        }
        return -1;
    }
};

方法三:

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
        if(S==T) return 0;
        unordered_map<int,vector<int>> r;
        
        int n=routes.size();
        for(int i=0 ;i<n;++i)
        {
            for(int route : routes[i])
            {
                r[route].push_back(i);                
            }
        }

        vector<bool> visited_route(n,false);
        queue<int> q;
        q.push(S);

        int dis=0;
        while(!q.empty())
        {
            ++dis;
            int m=q.size();
            while(m--)
            {
                int f=q.front();
                q.pop();
                for(int i:r[f])
                {
                    if(visited_route[i])continue;
                    visited_route[i]=true;
                    for(int j:routes[i])
                    {
                        if(j==T)return dis;
                        q.push(j);
                    }
                }
            }
        }

        return -1;
    }
};

0

评论区