加路後最短距離查詢 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中文網其他相關文章！