加路后最短距离查询 I

3243。加路后最短距离查询 I

难度：中等

主题：数组、广度优先搜索、图

给你一个整数 n 和一个二维整数数组查询。

有 n 个城市，编号从 0 到 n - 1。最初，对于所有 0 存在一条从城市 i 到城市 i 1 的单向

道路。 n - 1.

_{queries[i] = [u}i_{, v}i] 表示从城市 ui单向道路> 前往城市 v_i。每次查询后，您需要找到从城市 0 到城市 n - 1 的最短路径的长度。

返回一个数组answer，其中对于范围 [0,queries.length - 1] 中的每个 i，answer[i] 是处理 第一个我 1 个查询。

示例1：

• 输入： n = 5，查询 = [[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，查询 = [[0,3],[0,2]]
• 输出： [1,1]
• 说明： 加上0到3的路后，0到3的最短路径长度为1。 从0到2的路相加后，最短路径的长度仍然是1。

约束：

3 1 查询[i].length == 2
0 1 查询之间没有重复的道路。

提示：

1. 维护图并在每次更新后使用高效的最短路径算法。
2. 我们对每个查询使用 BFS/Dijkstra。

解决方案：

我们需要模拟在城市之间添加道路，并计算每次添加道路后从城市 0 到城市 n - 1 的最短路径。考虑到问题的约束和性质，我们可以使用广度优先搜索（BFS）来处理未加权的图。

方法：

1. 图形表示：

   • 我们可以使用邻接列表来表示城市和道路。最初，对于所有 0
   • 每次查询后，我们将从 u_i 到 v_i 的道路添加到图中。

2. 最短路径计算（BFS）：

   • 我们可以使用 BFS 计算从城市 0 到城市 n - 1 的最短路径。BFS 在这里效果很好，因为所有道路的权重相等（每条道路的长度为 1）。

3. 迭代查询：

   • 对于每个查询，我们将新的道路添加到图中，然后使用 BFS 查找从城市 0 到城市 n - 1 的最短路径。处理每个查询后，我们将结果存储在输出数组中。

4. 效率：

   • 由于我们在每次查询后都使用 BFS，并且图大小最多可以是 500 个城市，最多 500 个查询，因此每个 BFS 的时间复杂度为 O(n m)，其中 n 是城市数量，m 是道路数量。我们需要执行最多 500 次 BFS，这样解决方案才能在问题的约束下高效运行。

让我们用 PHP 实现这个解决方案：3243。加路后最短距离查询 I

<?php /**
 * @param Integer $n
 * @param Integer[][] $queries
 * @return Integer[]
 */
function shortestDistanceAfterQueries($n, $queries) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Function to find the shortest path using BFS
 *
 * @param $graph
 * @param $n
 * @return int
 */
function bfs($graph, $n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$n = 5;
$queries = [[2, 4], [0, 2], [0, 4]];
print_r(shortestDistanceAfterQueries($n, $queries));

// Example 2
$n = 4;
$queries = [[0, 3], [0, 2]];
print_r(shortestDistanceAfterQueries($n, $queries));
?>

解释：

1. 图初始化：

   • 邻接列表图用于表示城市和道路。
   • 最初，道路仅存在于连续城市之间（i 到 i 1）。

2. BFS 函数：

   • BFS 用于计算从城市 0 到城市 n - 1 的最短距离。我们维护一个 BFS 队列和一个距离数组来存储到达每个城市的最小道路（边）数。
   • 最初，到城市 0 的距离设置为 0，所有其他城市的距离为无穷大 (PHP_INT_MAX)。
   • 当我们处理 BFS 队列中的每个城市时，我们会更新其邻近城市的距离，并继续下去，直到访问完所有可到达的城市。

3. 查询处理：

   • 对于每个查询，新道路都会添加到图表中 (u -> v)。
   • 更新后调用BFS计算从城市0到城市n-1的最短路径
   • BFS 的结果存储在结果数组中。

4. 输出:

   • 结果数组包含每次查询后的最短路径长度。

5. 时间复杂度：

   • 每个 BFS 需要 O(n m)，其中 n 是城市数量，m 是道路数量。由于查询数量为 q，因此总体时间复杂度为 O(q * (n m))，这对于给定的约束应该是有效的。

演练示例：

对于输入 n = 5 且查询 = [[2, 4], [0, 2], [0, 4]]:

• 最初，道路是 [0 -> 1-> 2-> 3-> 4].
• 第一次查询 [2, 4] 后，道路为 [0 ->; 1-> 2-> 3-> 4]，从 0 到 4 的最短路径是 3（使用路径 0 -> 1 -> 2 -> 4）。
• 第二次查询 [0, 2] 后，道路为 [0 -> 2、 1-> 2-> 3-> 4]，从 0 到 4 的最短路径是 2（使用路径 0 -> 2 -> 4）。
• 第三次查询 [0, 4] 后，道路为 [0 -> 2、 1-> 2-> 3-> 4]，从 0 到 4 的最短路径是 1（直达道路 0 -> 4）。

因此，输出为 [3, 2, 1]。

最后的想法：

• 该解决方案对每个查询使用 BFS 来高效计算最短路径。
• 随着每个查询中添加新道路，图表会动态更新。
• 该解决方案在问题的限制范围内运行良好，可有效处理多达 500 个城市的多达 500 个查询。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是加路后最短距离查询 I的详细内容。更多信息请关注PHP中文网其他相关文章！