815. Bus Routes

问题:

给定多条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 };

 

上一篇:requests请求没返回数据的可能原因


下一篇:Demux 和 BusSelector 的区别