难度:困难。
标签:广度优先搜索,数组,哈希表。
这个题之前做过,印象深刻,还记得怎么做。
重点是要将公交车作为广搜的节点。使用公交站的话会超时。
正确解法:
class Solution {
public:
int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
if(source == target)return 0;
// one stop <-> buses
unordered_map<int, vector<int>> buses;
int bus_num = routes.size();
for(int i = 0; i < bus_num; ++i){
for(int j = 0; j < routes[i].size(); ++j){
buses[routes[i][j]].emplace_back(i);
}
}
queue<int> que;
unordered_set<int> visited;
int res = 1;
for(int i = 0; i < buses[source].size(); ++i){
que.push(buses[source][i]);
visited.insert(buses[source][i]);
}
while(!que.empty()){
int size = que.size();
for(int i = 0; i < size; ++i){
int bus = que.front();
que.pop();
for(int j = 0; j < routes[bus].size(); ++j){
int stop = routes[bus][j];
if(stop == target)return res;
for(int k = 0; k < buses[stop].size(); ++k){
if(visited.find(buses[stop][k]) == visited.end()){
que.push(buses[stop][k]);
visited.insert(buses[stop][k]);
}
}
}
}
res++;
}
return -1;
}
};
结果: