LeetCode 815.公交路线（BFS广搜 + 建图）（中秋快乐啊）
给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
- 例如，路线
routes[0] = [1, 5, 7]表示第0辆公交车会一直按序列1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ...这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
示例 1：
输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6 输出：2 解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
示例 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^5routes[i]中的所有值 互不相同sum(routes[i].length) <= 10^50 <= routes[i][j] < 10^60 <= source, target < 10^6
这道题的本质其实是dijkstra吧，但是他求得的是最少做几辆车那么可以转换成BFS来做，只要图建立出来了，基本就没啥问题了
遍历每一个站，把每一个站包含的车辆记录到一个数组当中，然后把起点的dist设置为0，从起点开始往后面一个个站去扩
代码
class Solution {static const int N = 1e6 + 10;int dist[N];
public:int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {int n = routes.size();unordered_map<int,vector<int>> station;for(int i = 0;i < n;i ++){for(int j = 0;j < routes[i].size();j ++){station[routes[i][j]].push_back(i);}}memset(dist,-1,sizeof(dist));dist[source] = 0;queue<int> q;q.push(source);while(!q.empty()){auto t = q.front();q.pop();for(auto x : station[t]){for(auto y : routes[x]){if(dist[y] == -1){dist[y] = dist[t] + 1;q.push(y);}}routes[x].clear();}}return dist[target];}
};中秋快乐
加油