加路後最短距離查詢 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))，這對於給定的限制應該是有效的。