题目描述
我们有一系列公交路线。每一条路线 routes[i] 上都有一辆公交车在上面循环行驶。
例如，有一条路线 routes[0] = [1, 5, 7]，表示第一辆 (下标为0)
公交车会一直按照 1->5->7->1->5->7->1->... 的车站路线行驶。
假设我们从 S 车站开始（初始时不在公交车上），要去往 T 站。
期间仅可乘坐公交车，求出最少乘坐的公交车数量。
返回 -1 表示不可能到达终点车站。
示例：
输入：
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
输出：2
解释：
最优策略是先乘坐第一辆公交车到达车站 7, 然后换乘第二辆公交车到车站 6。
提示：
1 <= routes.length <= 500.
1 <= routes[i].length <= 10^5.
0 <= routes[i][j] < 10 ^ 6.
算法1
使用路线作为图的点 而不是车站
然后求多终点多起点的最短路径
制图和求最短路径上各有手法 有哈希有双指针遍历核对路线有无相同车站
时间差距较大，我的哈希代码使用了unordered_set 才勉强通过，直接set就TLE了
C++ 代码
class Solution {
public:
vector<int> g[510];
unordered_set<int> stationOnLine[500];
int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
if (S == T) return 0;
for (int i = 0; i < routes.size(); i++) {
for (const auto& e : routes[i]) {
stationOnLine[i].insert(e);
}
}
for (int i = 0; i < routes.size(); i++) {
for (const auto& e : stationOnLine[i]) {
for (int j = i + 1; j < routes.size(); j++) {
if (stationOnLine[j].count(e) != 0) {
//两者连边
g[i].push_back(j); g[j].push_back(i);
}
}
}
}
vector<int> dis(routes.size(), INT_MAX);
queue<int> q;
for (int i = 0; i < routes.size(); i++) {
if (stationOnLine[i].count(S) != 0) {
//该路线包含起点站 放入队列中
q.push(i);
dis[i] = 1;
}
}
while (q.size()) {
int u = q.front();
q.pop();
if (stationOnLine[u].count(T) != 0) {
return dis[u];
}
for (auto v : g[u]) {
if (dis[v] > dis[u] + 1) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
return -1;
}
};
