跳至主要內容

3243. 新增道路查询后的最短距离 I

3243. 新增道路查询后的最短距离 I

🟠   🔖  广度优先搜索 图 数组  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given an integer n and a 2D integer array queries.

There are n cities numbered from 0 to n - 1. Initially, there is a unidirectional road from city i to city i + 1 for all 0 <= i < n - 1.

queries[i] = [ui, vi] represents the addition of a new unidirectional road from city ui to city vi. After each query, you need to find the length of the shortest path from city 0 to city n - 1.

Return an array answer where for each i in the range [0, queries.length - 1], answer[i] is the length of the shortest path from city 0 to city `n

  • 1 after processing the **first**i + 1` queries.

Example 1:

Input: n = 5, queries = [[2,4],[0,2],[0,4]]

Output: [3,2,1]

Explanation:

After the addition of the road from 2 to 4, the length of the shortest path from 0 to 4 is 3.

After the addition of the road from 0 to 2, the length of the shortest path from 0 to 4 is 2.

After the addition of the road from 0 to 4, the length of the shortest path from 0 to 4 is 1.

Example 2:

Input: n = 4, queries = [[0,3],[0,2]]

Output: [1,1]

Explanation:

After the addition of the road from 0 to 3, the length of the shortest path from 0 to 3 is 1.

After the addition of the road from 0 to 2, the length of the shortest path remains 1.

Constraints:

  • 3 <= n <= 500
  • 1 <= queries.length <= 500
  • queries[i].length == 2
  • 0 <= queries[i][0] < queries[i][1] < n
  • 1 < queries[i][1] - queries[i][0]
  • There are no repeated roads among the queries.

题目大意

给你一个整数 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] 中的每个 i，answer[i] 是处理完前i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的 长度 。

示例 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。

示例 2：

输入： n = 4, queries = [[0, 3], [0, 2]]

输出： [1, 1]

解释：

新增一条从 0 到 3 的道路后，从 0 到 3 的最短路径长度为 1。

新增一条从 0 到 2 的道路后，从 0 到 3 的最短路径长度仍为 1。

提示：

  • 3 <= n <= 500
  • 1 <= queries.length <= 500
  • queries[i].length == 2
  • 0 <= queries[i][0] < queries[i][1] < n
  • 1 < queries[i][1] - queries[i][0]
  • 查询中没有重复的道路。

解题思路

这是一道考察图遍历的题目，可以把每个城市看成图的一个节点，每条通路看成一条边。

  1. 初始化图的表示方式：

    • 使用 邻接表 存储图，邻接表用一个数组 road 表示，其中 road[i] 是节点 i 的所有邻居节点。
    • 初始图中只有链状路径 0 -> 1 -> 2 -> ... -> n-1。

  2. BFS 寻找最短路径：

    • 从节点 0 开始，用 队列 实现广度优先搜索。
    • 每次从队列中取出当前节点及其路径长度，访问其所有未访问的邻居节点。
    • 一旦访问到终点 n-1，即可返回当前路径长度，保证是最短的。

  3. 处理查询：

    • 遍历每个查询 (from, to)，将边 (from, to) 添加到邻接表中。
    • 调用 BFS 计算当前图中从节点 0 到节点 n-1 的最短路径，将结果存储到 res 数组中。

  4. 返回结果：

    • 遍历所有查询后，返回结果数组 res。

复杂度分析

  • 时间复杂度：O(q * (V + E))，每次查询执行 BFS，BFS 的复杂度为 O(V + E)，其中 V = n，E 是图中边数，q 是 queries 的长度，代表要查询 q 次。
  • 空间复杂度：O(V + E)，邻接表占用 O(V + E) 的空间，BFS 的队列和 visited 集合占用 O(V) 的空间。

代码

/**
 * @param {number} n
 * @param {number[][]} queries
 * @return {number[]}
 */
var shortestDistanceAfterQueries = function (n, queries) {
	// 初始化图，使用邻接表表示
	let road = new Array(n).fill().map((_, i) => [i + 1]);
	let res = [];

	// 计算最短路径的函数，使用 BFS
	const bfsShortestPath = () => {
		let queue = [[0, 0]]; // [节点, 距离]
		let visited = new Set();
		visited.add(0);

		while (queue.length) {
			let [node, dist] = queue.shift();

			// 如果找到目标节点，返回距离
			if (node === n - 1) return dist;

			// 遍历邻接节点
			for (let neighbor of road[node]) {
				if (!visited.has(neighbor)) {
					visited.add(neighbor);
					queue.push([neighbor, dist + 1]);
				}
			}
		}
	};

	// 处理每次查询
	for (let [from, to] of queries) {
		// 添加新边
		road[from].push(to);
		// 计算当前最短路径
		res.push(bfsShortestPath());
	}

	return res;
};