问题:
给定多条bus线路,routes[i]代表 bus i 的所有经停站点。
给定source起始站,和target目标站,求最少换乘几辆车能到达目的地。
Example 1: Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6 Output: 2 Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6. Example 2: Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12 Output: -1 Constraints: 1 <= routes.length <= 500. 1 <= routes[i].length <= 105 All the values of routes[i] are unique. sum(routes[i].length) <= 105 0 <= routes[i][j] < 106 0 <= source, target < 106
解法:BFS
分析:本问题中,
- 经过的站点,不再经过,
- 坐过的线路,也不再乘坐。
因此可使用两个visited数组,来标记已经乘坐过的线路or经过的站点。
通过给定的线路信息,构造站点上的所有bus结构体
- unordered_map<int,vector<int>> stop_buses;//dest, bus_no
- stop_buses[i]代表 站点 i 上可换乘的所有bus。
将当前所在的站点,入队。
- queue.push(source);
- 同时标记该站点访问过,visited.insert(source)
遍历队列,
- 每一层为换乘一次。res++
- 对于当前站点cur_stop:
- 若==target,那么已经以最少换乘次数到达目标地点。返回res。
- 否则在当前站点,开始尝试所有未尝试过的bus。
- bus_i : stop_buses[cur_stop]
- 对这些bus_i中,的任意一站 stop_i : bus_i
- (未停过的站点:visited[stop_i]不存在)
- 加入尝试下车站点。queue.push(stop_i)
- 尝试过该bus_i中的所有站点后,将这条线路清空,(以后其他尝试方法,不再尝试这条线路,本次尝试已经尝试过该条线路,以最少换乘)
代码参考:
1 class Solution { 2 public: 3 int numBusesToDestination(vector<vector<int>>& routes, int source, int target) { 4 unordered_map<int,vector<int>> stop_buses;//dest, bus_no 5 for(int i=0; i<routes.size(); i++) {//bus[i] 6 for(auto stp:routes[i]) {//every stop in this bus 7 stop_buses[stp].push_back(i); 8 } 9 } 10 int res = 0; 11 unordered_set<int> visited_stop; 12 queue<int> q;//stop 13 q.push(source); 14 visited_stop.insert(source); 15 while(!q.empty()) { 16 int sz = q.size(); 17 for(int i=0; i<sz; i++) { 18 int cur_stop = q.front(); 19 q.pop(); 20 if(cur_stop == target) return res; 21 for(int b:stop_buses[cur_stop]) {//choose bus 22 for(int stop:routes[b]) {//every stop in this bus route 23 if(visited_stop.insert(stop).second) { 24 q.push(stop); 25 } 26 } 27 routes[b].clear(); 28 //one bus only to take once. 29 } 30 } 31 res++; 32 } 33 return -1; 34 } 35 };