题目描述
我们有一系列公交路线。每一条路线 上都有一辆公交车在上面循环行驶。例如，有一条路线 ，表示第一辆（下标为 ）公交车会一直按照 的车站路线行驶。
假设我们从 车站开始（初始时不在公交车上），要去往 站。期间仅可乘坐公交车，求出最少乘坐的公交车数量。返回 表示不可能到达终点车站。
示例1
输入： routes = [[1, 2, 7], [3, 6, 7]] S = 1 T = 6 输出： 2 解释： 最优策略是先乘坐第一辆公交车到达车站 7, 然后换乘第二辆公交车到车站 6。
题解
我们可以将每一条线路视作一个点，对于任意两条线路，如果它们经过的车站有交集，那么就在两点之间连一条边，这样就构成了一张图。
图中有些点（路线）是包含起点 的，我们把它们都作为起点。而有些点（路线）是包含终点 的，我们把它们都作为终点。
那么问题就转化为了求起点到终点的最短路径。因为起点和终点数量可能有多个，所以我们新建两个结点，一个起点用来指向所有包含 的点，一个终点用来指向所有包含 的点。接下来问题就变成了单源最短路径问题了。
因为本题中边并没有权值（或者说都是 ），那么我们就可以直接用 BFS 来进行求解最短路。
建图的时候，对于任意两条路线，我们要判断它们车站是否存在交集。可以事先对每条线路的车站编号进行排序，然后用双指针法判断。最好排完序还要去重，防止数据有重复。不过实际运行中，就算不排序也能通过，说明数据给的就是有序的了。
最终时间复杂度由几部分决定。假设路线数量是 ，每条路线最多有 个车站。那么排序复杂度为 ，建图复杂度为 ，BFS 复杂度为 。因此总的时间复杂度忽略低阶项之后为 。看起来貌似还是有点高，但其实建图的时候，大多数情况下双指针法并不会遍历完所有的车站，所以达不到 。
代码
c++
class Solution { public: int numBusesToDestination(vector<vector<int>>& routes, int S, int T) { if (S == T) return 0; int n = routes.size(); for (int i = 0; i < n; ++i) { sort(routes[i].begin(), routes[i].end()); routes[i].erase(unique(routes[i].begin(), routes[i].end()), routes[i].end()); } routes.push_back({S}); routes.push_back({T}); vector<vector<int>> G = buildGraph(routes, S, T); return BFS(G); } vector<vector<int>> buildGraph(vector<vector<int>>& routes, int S, int T) { int n = routes.size(); vector<vector<int>> G(n); for (int i = 0; i < n; ++i) { for (int j = i+1; j < n; ++j) { int su = routes[i].size(), sv = routes[j].size(); int u = 0, v = 0; while (u < su && v < sv) { if (routes[i][u] < routes[j][v]) ++u; else if (routes[i][u] > routes[j][v]) ++v; else { G[i].push_back(j); G[j].push_back(i); break; } } } } return G; } int BFS(vector<vector<int>>& G) { int n = G.size(); int S = n - 2; int T = n - 1; vector<int> dis(n, -1); queue<int> Q; Q.push(S); dis[S] = 0; while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int i = 0, sz = G[u].size(); i < sz; ++i) { int v = G[u][i]; if (dis[v] == -1) { Q.push(v); dis[v] = dis[u] + 1; if (v == T) return dis[v]-1; } } } return -1; } };
