Leetcode—815. 公交路线【困难】（unordered_map+queue）

2024每日刷题（163）

Leetcode—815. 公交路线

bfs实现代码

class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
        if(source == target) {
            return 0;
        }
        unordered_map<int, vector<int>> stop2bus;
        int m = routes.size();

        for(int i = 0; i < m; i++) {
            for(const auto stop: routes[i]) {
                stop2bus[stop].push_back(i);
            }
        }
        vector<bool> visited(501, false);
        queue<int> q;
        for(auto &bus: stop2bus[source]) {
            visited[bus] = true;
            q.push(bus);
        }

        int ans = 1;
        while(!q.empty()) {
            int size = q.size();
            while(size--) {
                int bus = q.front();
                q.pop();
                for(auto &stop: routes[bus]) {
                    if(stop == target) {
                        return ans;
                    }
                    for(auto &nextBus: stop2bus[stop]) {
                        if(visited[nextBus] == false) {
                            visited[nextBus] = true;
                            q.push(nextBus);
                        }
                    }
                }
            }
            ans++;
        }
        return -1;
    }
};

运行结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！