新校区建设网站管理规定,网络营销方案设计题,国外教做蛋糕的网站,建设一个网站需要多久多少钱目录 题目描述#xff1a;示例 #xff1a;代码实现#xff1a; 题目描述#xff1a;
给你一个整数 n 和一个二维整数数组 queries。 有 n 个城市#xff0c;编号从 0 到 n - 1。初始时#xff0c;每个城市 i 都有一条单向道路通往城市 i 1#xff08; 0 i … 目录 题目描述示例 代码实现 题目描述
给你一个整数 n 和一个二维整数数组 queries。 有 n 个城市编号从 0 到 n - 1。初始时每个城市 i 都有一条单向道路通往城市 i 1 0 i n - 1。 queries[i] [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后你需要找到从城市 0 到城市 n - 1 的最短路径的长度。 返回一个数组 answer对于范围 [0, queries.length - 1] 中的每个 ianswer[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。
代码实现
class Solution {public int[] shortestDistanceAfterQueries(int n, int[][] queries) {// 初始化答案列表ListInteger answer new ArrayList();// 初始化图表示当前点能到达其他位置的集合ListListInteger 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个城市可以到达第i1个城市}// 处理每一个查询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));}// 将列表转换为数组int[] res new int[answer.size()];for (int i 0; i answer.size(); i) {res[i] answer.get(i);}return res;}int bfsShortestPath(ListListInteger graph, int n) {// 队列用于BFSQueueInteger queue new LinkedList();// 距离数组用于记录从0到其他节点的距离int[] dist new int[n];Arrays.fill(dist, Integer.MAX_VALUE);// 将dist数组所有元素初始化为Integer中的最大值dist[0] 0;// 初始化0到第0个城市距离为0queue.offer(0);// 入队// 从0开始广度优先搜索队列内元素while (!queue.isEmpty()) {// 当队列为空时跳出循环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数组中尾部元素即当前路径中0到n-1的最短距离}
}
