道路追加クエリ後の最短距離 I

3243。道路追加クエリ後の最短距離 I

難易度: 中

トピック: 配列、幅優先検索、グラフ

整数 n と 2D 整数配列クエリが与えられます。

0 から n - 1 までの番号が付けられた n 個の都市があります。最初は、すべての 0 一方向 道路があります。 n - 1.

queries[i] = [u_i, v_i] は、都市 ui一方向_{道路の追加を表します。 > 都市v}i_{へ。各クエリの後で、都市 0 から都市 n - 1 までの}最短パスの長さを見つける必要があります。

範囲 [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/ダイクストラを使用します。

解決策:

都市間の道路の追加をシミュレートし、各道路の追加後に都市 0 から都市 n - 1 までの最短パスを計算する必要があります。制約と問題の性質を考慮すると、重み付けされていないグラフに対して 幅優先検索 (BFS) を使用できます。

アプローチ：

1. グラフ表現:

   • 隣接リストを使用して都市と道路を表すことができます。最初に、各都市 i には、すべて 0
   • 各クエリの後、u_i から v_i への道路をグラフに追加します。

2. 最短パス計算 (BFS):

   • BFS を使用して、都市 0 から都市 n - 1 までの最短パスを計算できます。すべての道路の重みが等しい (各道路の長さは 1) ため、BFS はここでうまく機能します。

3. クエリの反復:

   • クエリごとに、新しい道路をグラフに追加し、BFS を使用して都市 0 から都市 n - 1 までの最短パスを見つけます。各クエリを処理した後、結果を出力配列に保存します。

4. 効率:

   • 各クエリの後に BFS を使用しており、グラフ サイズは最大 500 のクエリで最大 500 の都市にできるため、各 BFS の時間計算量は O(n m) です。ここで、n は都市の数、m は道路の数。問題の制約内でソリューションが効率的に実行されるように、BFS を最大 500 回実行する必要があります。

このソリューションを 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)。
   • 更新後に都市 0 から都市 n-1 までの最短パスを計算するために BFS が呼び出されます。
   • 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 を使用)。
• 2 番目のクエリ [0, 2] の後、道路は [0 ->; 2、1 -> 2 -> 3 -> 4]、0 から 4 への最短パスは 2 です (パス 0 -> 2 -> 4 を使用)。
• 3 番目のクエリ [0, 4] の後、道路は [0 ->; 2、1 -> 2 -> 3 -> 4]、0 から 4 への最短経路は 1 (直線道路 0 -> 4) です。

したがって、出力は [3, 2, 1] となります。

最終的な考え:

• このソリューションでは、クエリごとに BFS を使用して最短パスを効率的に計算します。
• 各クエリに新しい道路が追加されると、グラフは動的に更新されます。
• このソリューションは問題の制約内でうまく機能し、最大 500 の都市で最大 500 のクエリを効率的に処理します。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が道路追加クエリ後の最短距離 Iの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。