我们有一系列公交路线。每一条路线 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 <= 500.
0 <= routes[i][j] < 10 ^ 6.
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/bus-routes 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
if(S == T)//哈哈,又被坑了
return 0;
unordered_map<int,unordered_set<int>> station_line;//站点,线路
unordered_map<int,unordered_set<int>> line_station;//线路,站点
queue<int> q;//线路队列
int n = routes.size(), line, station, step = 1, size;
unordered_set<int> visitedStation;
unordered_set<int> visitedLine;
for(int i = 0, j; i < n; ++i)
{
for(j = 0; j < routes[i].size(); ++j)
{
station_line[routes[i][j]].insert(i);
line_station[i].insert(routes[i][j]);
if(routes[i][j] == S)
{
q.push(i);//起点站的线路,都放进队列
visitedStation.insert(S);
visitedLine.insert(i);
}
}
}
while(!q.empty())
{
size = q.size();
while(size--)
{
line = q.front();
q.pop();
if(line_station[line].count(T))
return step;//线路包含终点,返回
for(auto st = line_station[line].begin(); st != line_station[line].end(); ++st)
{ //查找这条线路经过的所有站
if(!visitedStation.count(*st))
{ //没访问过的站
visitedStation.insert(*st);
for(auto l = station_line[*st].begin(); l != station_line[*st].end(); ++l)
{ //这个站的所有未访问线路
if(!visitedLine.count(*l))
{
q.push(*l);
visitedLine.insert(*l);
}
}
}
}
}
step++;
}
return -1;
}
};
444 ms 59.5 MB