題目描述：

給你一個整數(shù) n 和一個二維整數(shù)數(shù)組 queries。
有 n 個城市，編號從 0 到 n - 1。初始時，每個城市 i 都有一條單向道路通往城市 i + 1（ 0 <= i < n - 1）。
queries[i] = [ui, vi] 表示新建一條從城市 ui 到城市 vi 的單向道路。每次查詢后，你需要找到從城市 0 到城市 n - 1 的最短路徑的長度。
返回一個數(shù)組 answer，對于范圍 [0, queries.length - 1] 中的每個 i，answer[i] 是處理完前 i + 1 個查詢后，從城市 0 到城市 n - 1 的最短路徑的長度。

示例 ：

輸入： n = 5, queries = [[2, 4], [0, 2], [0, 4]]
輸出： [3, 2, 1]
解釋：

新增一條從 2 到 4 的道路后，從 0 到 4 的最短路徑長度為 3。

新增一條從 0 到 2 的道路后，從 0 到 4 的最短路徑長度為 2。

新增一條從 0 到 4 的道路后，從 0 到 4 的最短路徑長度為 1。

代碼實現(xiàn)：

class Solution {public int[] shortestDistanceAfterQueries(int n, int[][] queries) {// 初始化答案列表List<Integer> answer = new ArrayList<>();// 初始化圖：表示當前點能到達其他位置的集合List<List<Integer>> graph = new ArrayList<>();for (int i = 0; i < n; i++) {graph.add(new ArrayList<>());// 添加0到n-1個城市}// 添加初始的單向邊for (int i = 0; i < n - 1; i++) {graph.get(i).add(i + 1);// 表示第i個城市可以到達第i+1個城市}// 處理每一個查詢for (int[] query : queries) {int u = query[0];// 起點int v = query[1];// 終點// 添加新建的單向邊graph.get(u).add(v);// 使用BFS計算從城市0到城市n-1的最短路徑長度answer.add(bfsShortestPath(graph, n));}// 將列表轉(zhuǎn)換為數(shù)組int[] res = new int[answer.size()];for (int i = 0; i < answer.size(); i++) {res[i] = answer.get(i);}return res;}int bfsShortestPath(List<List<Integer>> graph, int n) {// 隊列用于BFSQueue<Integer> queue = new LinkedList<>();// 距離數(shù)組用于記錄從0到其他節(jié)點的距離int[] dist = new int[n];Arrays.fill(dist, Integer.MAX_VALUE);// 將dist數(shù)組所有元素初始化為Integer中的最大值dist[0] = 0;// 初始化0到第0個城市，距離為0queue.offer(0);// 入隊// 從0開始廣度優(yōu)先搜索隊列內(nèi)元素while (!queue.isEmpty()) {// 當隊列為空時，跳出循環(huán)int current = queue.poll();// 出隊當前隊頭元素for (int neighbor : graph.get(current)) {// 遍歷當前隊頭元素在圖上可達鄰點if (dist[neighbor] == Integer.MAX_VALUE) {// 如果鄰點為初始值時dist[neighbor] = dist[current] + 1;// 更新最短距離queue.offer(neighbor);// 并且讓鄰點入隊}}}return dist[n - 1];// 返回dist數(shù)組中尾部元素，即當前路徑中0到n-1的最短距離}
}