Leetcode: 815 公交路线

https://leetcode-cn.com/submissions/detail/25642457/

class Solution {
    public int numBusesToDestination(int[][] routes, int S, int T) {
        if (S == T) { // 如果起点 == 终点 return
            return 0;
        } 
        
        // 根据公交车节点和公交站点节点建立关系
        Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
        for (int i = 0; i< routes.length; ++ i) {
            for (int j: routes[i]) { // j  = 公交站点
                if (!map.containsKey(j)) { // 不包含的公交站点则加入 map
                    map.put(j, new HashSet<Integer>()); // 默认初始值为0
                }
                map.get(j).add(i);
            }
        }
        
        // 从起点开始, 吧所有符合公交车站点节点S的对应公交车加入queue中
        Queue<Integer> queue = new LinkedList<Integer>();
        Set<Integer> visited = new HashSet<Integer>();
        for (int st: map.get(S)) {
            queue.offer(st);
            visited.add(st);
        }
        
        int ans = 1;
        
        while(!queue.isEmpty()) {// 知道队列为空
            Queue<Integer> t = new LinkedList<Integer>();
            while(!queue.isEmpty()) {
                int currentCar = queue.poll();
                for (int k: routes[currentCar]) {// 遍历链接的公交车站节点
                    if (k == T) {
                        return ans;
                    }
                    for (int nextCar : map.get(k)) { // 便利当前公交车站点所有的公交车借点
                        if (!visited.contains(nextCar)) {// 未访问过的
                            t.offer(nextCar);
                            visited.add(nextCar);
                        }
                    }
                }
            }
            ++ ans;
            queue = t;
        }
        
        return -1;
        
    }
}