-
1 <= routes.length <= 500. 1 <= routes[i].length <= 105- All the values of
routes[i]are unique. sum(routes[i].length) <= 1050 <= routes[i][j] < 1060 <= source, target < 106
BFS的hard题，几百年没做过BFS了不会，复习完BFS还是不会，啊。
这题首先需要考虑怎么去构造这个可以用来BFS的数据结构。题目给的是每个route里有哪些stop，但是我们需要知道的是stop怎么去找下一个stop，所以刚开始我的想法就是构造一个map，key是stop，value是a list of next stops。这样的想法其实也是可以的，但是在stops巨多的情况下就很容易TLE了（抄完答案回来改这个做法以后发现其实是work的，但是submit的时候在一个有9w个stop要求从0到9w的case TLE了）。抄答案的做法构造的是stop到经过它的route的index的map，这就显然比记录所有next stop要lightweight很多。有一个语法上的小技巧，就是在构造这个Map<Integer, List<Integer>>的时候，想要往list里加东西可以不需要重新put一个list进去，而可以直接get().add()来操作这个list。
构造完数据结构以后就是常规BFS了。需要考虑这个queue里放什么。很直观应该用stop，但是因为前面构造的map是to route的所以刚开始被confuse到了，其实还是应该是a queue of stop。常规先把source加进queue，while queue is not empty，get size of queue，然后for loop for each element in the queue，这个for loop里面就要看看这个stop能去哪些route，如果这些route里有target那就可以快乐return 层数which is result了。不然就把这些stop都pop进queue，下一层再来看看。
还有一个点就是还需要用一个visited set来存放已经visited的route，不然就会死循环？
最后就是一些corner case，比如source == target的时候，进到我们的循环里以后会return result + 1就会是1，所以需要拎出来单独处理。
class Solution {
public int numBusesToDestination(int[][] routes, int source, int target) {
// we need to deal with this case explicity
if (source == target) {
return 0;
}
// store each stop and the bus route index that stops at the stop
Map<Integer, List<Integer>> stopToRoutes = new HashMap<>();
for (int i = 0; i < routes.length; i++) {
for (int stop : routes[i]) {
stopToRoutes.putIfAbsent(stop, new ArrayList<>());
stopToRoutes.get(stop).add(i);
}
}
// BFS to iterate through all the routes
int result = 0;
Queue<Integer> stopQueue = new ArrayDeque<>();
Set<Integer> visitedRoute = new HashSet<>();
stopQueue.add(source);
while (!stopQueue.isEmpty()) {
int size = stopQueue.size();
for (int i = 0; i < size; i++) {
int currStop = stopQueue.remove();
// need to deal with the case when there is no route from the source explicitly
// otherwise the get(stop) will be null
List<Integer> canGoToRoute = stopToRoutes.getOrDefault(currStop, new ArrayList<>());
for (int route : canGoToRoute) {
// don't want to visit the same route again
if (visitedRoute.contains(route)) {
continue;
}
visitedRoute.add(route);
for (int stop : routes[route]) {
if (stop == target) {
return result + 1;
}
stopQueue.add(stop);
}
}
}
result++;
}
return -1;
}
}