1. 题目
我们有一系列公交路线。每一条路线 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 = 1T = 6输出: 2解释: 最优策略是先乘坐第一辆公交车到达车站 7, 然后换乘第二辆公交车到车站 6。说明:1 <= routes.length <= 500.1 <= routes[i].length <= 500.0 <= routes[i][j] < 10 ^ 6.
来源：力扣（LeetCode） 链接：https://leetcode-/problems/bus-routes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
class Solution {public:int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {if(S == T)//哈哈，又被坑了return 0;unordered_map<int,unordered_set<int>> station_line;//站点，线路unordered_map<int,unordered_set<int>> line_station;//线路，站点queue<int> q;//线路队列int n = routes.size(), line, station, step = 1, size;unordered_set<int> visitedStation;unordered_set<int> visitedLine;for(int i = 0, j; i < n; ++i){for(j = 0; j < routes[i].size(); ++j){station_line[routes[i][j]].insert(i);line_station[i].insert(routes[i][j]);if(routes[i][j] == S){q.push(i);//起点站的线路，都放进队列visitedStation.insert(S);visitedLine.insert(i);}}}while(!q.empty()){size = q.size();while(size--){line = q.front();q.pop();if(line_station[line].count(T))return step;//线路包含终点，返回for(auto st = line_station[line].begin(); st != line_station[line].end(); ++st){//查找这条线路经过的所有站if(!visitedStation.count(*st)){//没访问过的站visitedStation.insert(*st);for(auto l = station_line[*st].begin(); l != station_line[*st].end(); ++l){//这个站的所有未访问线路if(!visitedLine.count(*l)){q.push(*l);visitedLine.insert(*l);}}}}}step++;}return -1;}};
444 ms 59.5 MB
如果觉得《LeetCode 815. 公交路线（最少换乘 BFS）》对你有帮助，请点赞、收藏，并留下你的观点哦！
