815. 公交路线（24.9.17）

题目

给你一个数组 routes，表示一系列公交线路。其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。例如，路线 routes[0]=[1,5,7] 表示第 0 辆公交车会一直按序列 1->5->7->1->5->7->1->... 这样的车站路线行驶。现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。期间仅可乘坐公交车。求出最少乘坐的公交车数量。如果不可能到达终点车站，返回 -1。

示例：

1. 示例 1：
   • 输入：routes=[[1,2,7], [3,6,7]]，source=1，target=6
   • 输出：2
   • 解释：最优策略是先乘坐第一辆公交车到达车站 7，然后换乘第二辆公交车到车站 6。
2. 示例 2：
   • 输入：routes =[[7,12],[4,5,15],[6],[15,19],[9,12,13]]，source=15，target =12
   • 输出：-1

提示：

• 1 <= routes.length <= 500。
• 1 <= routes[i].length <= 10^5。
• routes[i] 中的所有值互不相同。
• sum(routes[i].length) <= 10^5。
• 0 <= routes[i][j] < 10^6。
• 0 <= source, target < 10^6。

解题思路

见代码

代码

class Solution {
public:int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {//记录每个公交站台可以通过的公交编号unordered_map<int,vector<int>> h;for(int i=0;i<routes.size();i++){for(int j:routes[i]){h[j].push_back(i);}}//如果没有经过 source 或者 target的公交，则可以直接返回//注：0 <= source, target < 10^6 其中包括了 source == target 的情况//如果两者不相等则说明不存在路径，如果相等则说明不需要乘坐任何一辆公交车了if(!h.contains(source)||!h.contains(target)){if(source==target) return 0;else return -1;//此处可以写成： return source != target ? -1 : 0;} //BFS部分 （广度优先搜索部分）unordered_map<int,int> end;//记录终点站（假设为a）要几路公交vector<int> v(routes.size());//用于记录是否访问过queue<int> q;q.push(source);while (!q.empty()){int k=q.front();//取第一站点 k,作为当前站点q.pop();//遍历经过k站的公交车for(int j:h[k]){int end_a=end[k];//遍历j路公交的路所经过的站点 a//如果存在则说明访问过了，则不需要访问了if(v[j]==0){for(int a:routes[j]){if(!end.contains(a)){end[a]=end_a+1;q.push(a);}}}v[j]=1;//用于表示我已经访问过该路车了}}return end.contains(target)?end[target]:-1;//查看是否有target的记录，如果没有则说明找不到此路，返回-1}
};