题目：
给你一个数组 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 <= 105routes[i]中的所有值 互不相同sum(routes[i].length) <= 1050 <= routes[i][j] < 1060 <= source, target < 106
以公交站为节点构建图
思路：
通过领接表存储每个公交站可以直接到达的其他公交站点，然后广度优先搜索出来最短路径即可
代码：
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
// 构建图，然后广度优先搜索（无向图）
if (source == target) return 0;
unordered_map<int, set<int>> graph; // 每个公交站可以直接到达的其他公交站
for (int i = 0; i < routes.size(); i++) {
for (int j = 0; j < routes[i].size(); j++) {
for (int k = j + 1; k < routes[i].size(); k++) {
if (graph[routes[i][j]].count(routes[i][k])) continue;
graph[routes[i][j]].insert(routes[i][k]);
graph[routes[i][k]].insert(routes[i][j]);
}
}
}
unordered_set<int> visited;
queue<int> que;
int ans = 0;
que.push(source);
visited.insert(source);
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
int top = que.front();
que.pop();
if (top == target) return ans;
for (int next : graph[top]) {
if (visited.find(next) == visited.end()) {
// 没访问过
que.push(next);
visited.insert(next);
}
}
}
ans++;
}
return -1;
}
};
记录每个站点可乘公交车编号
思路：
代码实现时，为方便起见，车站编号是一个一个出队的。
有哪些公交车会经过车站 x？
创建一个哈希表 stopToBuses，key 为车站编号，value 为经过该车站的公交车编号列表。
遍历第 i 辆公交车的路线 routes[i]，对于车站 x = routes[i][j]，把公交车编号 i 加到 stopToBuses[x] 列表中。
在 BFS 中，如何保证每辆公交车的路线只遍历一次？
可以创建一个 vis 数组。更简单的办法是，当公交车路线 routes[i] 遍历结束后，把 routes[i] 置为空。
在 BFS 中，如何保证每个车站只入队一次？
为了记录起点到每个站的最短路（最少乘坐的公交车数量），创建一个哈希表 dis，key 为车站编号，value 为起点到该车站的最短路。
我们可以利用 dis 来知道车站 x 是否入队过：看 x 是否在 dis 中即可。
小优化
如果没有公交车经过起点或终点，直接返回：
如果 source != target，无法从起点到达终点，返回 −1。
如果 source=target，返回 0。
代码：
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
// 记录经过车站 x 的公交车编号
unordered_map<int, vector<int>> stop_to_buses;
for (int i = 0; i < routes.size(); i++) {
for (int x : routes[i]) {
stop_to_buses[x].push_back(i);
}
}
// 小优化：如果没有公交车经过起点或终点，直接返回
if (!stop_to_buses.contains(source) || !stop_to_buses.contains(target)) {
// 注意原地 TP 的情况
return source != target ? -1 : 0;
}
// BFS
unordered_map<int, int> dis;
dis[source] = 0;
queue<int> q;
q.push(source);
while (!q.empty()) {
int x = q.front(); // 当前在车站 x
q.pop();
int dis_x = dis[x];
for (int i : stop_to_buses[x]) { // 遍历所有经过车站 x 的公交车 i
for (int y : routes[i]) { // 遍历公交车 i 的路线
if (!dis.contains(y)) { // 没有访问过车站 y
dis[y] = dis_x + 1; // 从 x 站上车然后在 y 站下车
q.push(y);
}
}
routes[i].clear(); // 标记 routes[i] 遍历过，做过一次这个车了，没必要再做
}
}
return dis.contains(target) ? dis[target] : -1;
}
};