加路后最短距离查询 I-php教程-PHP中文网

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。

约束：

提示：

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

解决方案：

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

方法：

图形表示：
- 我们可以使用邻接列表来表示城市和道路。最初，对于所有 0
- 每次查询后，我们将从 u_i 到 v_i 的道路添加到图中。
最短路径计算（BFS）：
- 我们可以使用 BFS 计算从城市 0 到城市 n - 1 的最短路径。BFS 在这里效果很好，因为所有道路的权重相等（每条道路的长度为 1）。
迭代查询：
- 对于每个查询，我们将新的道路添加到图中，然后使用 BFS 查找从城市 0 到城市 n - 1 的最短路径。处理每个查询后，我们将结果存储在输出数组中。
效率：
- 由于我们在每次查询后都使用 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));
?>

登录后复制

解释：

图初始化：
- 邻接列表图用于表示城市和道路。
- 最初，道路仅存在于连续城市之间（i 到 i 1）。
BFS 函数：
- BFS 用于计算从城市 0 到城市 n - 1 的最短距离。我们维护一个 BFS 队列和一个距离数组来存储到达每个城市的最小道路（边）数。
- 最初，到城市 0 的距离设置为 0，所有其他城市的距离为无穷大 (PHP_INT_MAX)。
- 当我们处理 BFS 队列中的每个城市时，我们会更新其邻近城市的距离，并继续下去，直到访问完所有可到达的城市。
查询处理：
- 对于每个查询，新道路都会添加到图表中 (u -> v)。
- 更新后调用BFS计算从城市0到城市n-1的最短路径
- BFS 的结果存储在结果数组中。
输出:
- 结果数组包含每次查询后的最短路径长度。
时间复杂度：
- 每个 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]。