淄博网站建设乐达,鞍山seo公司,沧州企业网站,海西州电子商务网站建设1. 题目
我们有一系列公交路线。每一条路线 routes[i] 上都有一辆公交车在上面循环行驶。 例如#xff0c;有一条路线 routes[0] [1, 5, 7]#xff0c;表示第一辆 (下标为0) 公交车会一直按照 1-5-7-1-5-7-1-… 的车站路线行驶。
假设我们从 …1. 题目
我们有一系列公交路线。每一条路线 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 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
class Solution {
public:int numBusesToDestination(vectorvectorint routes, int S, int T) {if(S T)//哈哈又被坑了return 0;unordered_mapint,unordered_setint station_line;//站点线路unordered_mapint,unordered_setint line_station;//线路站点queueint q;//线路队列int n routes.size(), line, station, step 1, size;unordered_setint visitedStation;unordered_setint 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
