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;}
};

运行结果

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