https://leetcode-cn.com/submissions/detail/25642457/
class Solution {
public int numBusesToDestination(int[][] routes, int S, int T) {
if (S == T) { // 如果起點 == 終點 return
return 0;
}
// 根據(jù)公交車節(jié)點和公交站點節(jié)點建立關(guān)系
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);
}
}
// 從起點開始, 吧所有符合公交車站點節(jié)點S的對應(yīng)公交車加入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]) {// 遍歷鏈接的公交車站節(jié)點
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;
}
}
