Jarak Terpendek Selepas Pertanyaan Penambahan Jalan I

3243. Jarak Terpendek Selepas Pertanyaan Penambahan Jalan I

Kesukaran: Sederhana

Topik: Tatasusunan, Keluasan-Carian Pertama, Graf

Anda diberi pertanyaan tatasusunan integer n dan integer 2D.

Terdapat n bandar bernombor dari 0 hingga n - 1. Pada mulanya, terdapat jalan sehala dari bandar i ke bandar i 1 untuk semua 0

pertanyaan[i] = [u_i, v_i] mewakili penambahan jalan sehala baharu dari bandar u_i ke bandar v_i. Selepas setiap pertanyaan, anda perlu mencari panjang laluan terpendek dari bandar 0 ke bandar n - 1.

Kembalikan jawapan tatasusunan di mana bagi setiap i dalam julat [0, queries.length - 1], answer[i] ialah panjang laluan terpendek dari bandar 0 ke bandar n - 1 selepas memproses pertama i 1 pertanyaan.

Contoh 1:

• Input: n = 5, pertanyaan = [[2,4],[0,2],[0,4]]
• Output: [3,2,1]
• Penjelasan: Selepas penambahan jalan dari 2 kepada 4, panjang laluan terpendek dari 0 hingga 4 ialah 3. Selepas penambahan jalan dari 0 kepada 2, panjang laluan terpendek dari 0 hingga 4 ialah 2. Selepas penambahan jalan dari 0 kepada 4, panjang laluan terpendek dari 0 hingga 4 ialah 1.

Contoh 2:

• Input: n = 4, pertanyaan = [[0,3],[0,2]]
• Output: [1,1]
• Penjelasan: Selepas penambahan jalan dari 0 hingga 3, panjang laluan terpendek dari 0 hingga 3 ialah 1. Selepas penambahan jalan dari 0 kepada 2, panjang laluan terpendek kekal 1.

Kekangan:

• 3
• 1
• pertanyaan[i].panjang == 2
• 0
• 1
• Tiada jalan berulang antara pertanyaan.

Petunjuk:

1. Kekalkan graf dan gunakan algoritma laluan terpendek yang cekap selepas setiap kemas kini.
2. Kami menggunakan BFS/Dijkstra untuk setiap pertanyaan.

Penyelesaian:

Kami perlu mensimulasikan penambahan jalan antara bandar dan mengira laluan terpendek dari bandar 0 ke bandar n - 1 selepas setiap penambahan jalan. Memandangkan kekangan dan sifat masalah, kami boleh menggunakan Breadth-First Search (BFS) untuk graf tidak berwajaran.

Pendekatan:

1. Perwakilan Graf:

   • Kami boleh mewakili bandar dan jalan raya menggunakan senarai bersebelahan. Pada mulanya, setiap bandar i akan mempunyai jalan ke bandar i 1 untuk semua 0
   • Selepas setiap pertanyaan, kami menambah jalan dari u_i ke v_i ke dalam graf.

2. Pengiraan Laluan Terpendek (BFS):

   • Kita boleh menggunakan BFS untuk mengira laluan terpendek dari bandar 0 ke bandar n - 1. BFS berfungsi dengan baik di sini kerana semua jalan mempunyai berat yang sama (setiap jalan mempunyai panjang 1).

3. Lelaran atas Pertanyaan:

   • Untuk setiap pertanyaan, kami akan menambah jalan baharu pada graf dan kemudian menggunakan BFS untuk mencari laluan terpendek dari bandar 0 ke bandar n - 1. Selepas memproses setiap pertanyaan, kami menyimpan hasilnya dalam tatasusunan output.

4. Kecekapan:

   • Memandangkan kami menggunakan BFS selepas setiap pertanyaan, dan saiz graf boleh paling banyak 500 bandar dengan sehingga 500 pertanyaan, kerumitan masa untuk setiap BFS ialah O(n m), dengan n ialah bilangan bandar dan m ialah bilangan jalan raya. Kita perlu melakukan BFS sehingga 500 kali, jadi penyelesaian akan berjalan dengan cekap dalam kekangan masalah.

Mari laksanakan penyelesaian ini dalam PHP: 3243. Jarak Terpendek Selepas Pertanyaan Penambahan Jalan 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));
?>

Penjelasan:

1. Permulaan Graf:

   • Graf senarai bersebelahan digunakan untuk mewakili bandar dan jalan raya.
   • Pada mulanya, jalan raya hanya wujud antara bandar berturut-turut (i hingga i 1).

2. Fungsi BFS:

   • BFS digunakan untuk mengira jarak terpendek dari bandar 0 ke bandar n - 1. Kami mengekalkan baris gilir untuk BFS dan jarak tatasusunan untuk menyimpan bilangan minimum jalan (tepi) untuk sampai ke setiap bandar.
   • Pada mulanya, jarak ke bandar 0 ditetapkan kepada 0 dan semua bandar lain mempunyai jarak infiniti (PHP_INT_MAX).
   • Semasa kami memproses setiap bandar dalam baris gilir BFS, kami mengemas kini jarak untuk bandar jirannya dan meneruskan sehingga semua bandar yang boleh dicapai dilawati.

3. Pemprosesan Pertanyaan:

   • Untuk setiap pertanyaan, jalan baharu ditambahkan pada graf (u -> v).
   • BFS dipanggil untuk mengira laluan terpendek dari bandar 0 ke bandar n-1 selepas kemas kini.
   • Hasil BFS disimpan dalam tatasusunan hasil.

4. Output:

   • Tatasusunan hasil mengandungi panjang laluan terpendek selepas setiap pertanyaan.

5. Kerumitan Masa:

   • Setiap BFS mengambil O(n m), dengan n ialah bilangan bandar dan m ialah bilangan jalan. Memandangkan bilangan pertanyaan ialah q, kerumitan masa keseluruhan ialah O(q * (n m)), yang sepatutnya cekap untuk kekangan yang diberikan.

Contoh Panduan:

Untuk input n = 5 dan pertanyaan = [[2, 4], [0, 2], [0, 4]]:

• Pada mulanya, jalan raya adalah [0 -> 1 -> 2 -> 3 -> 4].
• Selepas pertanyaan pertama [2, 4], jalan ialah [0 -> 1 -> 2 -> 3 -> 4] dan laluan terpendek dari 0 hingga 4 ialah 3 (menggunakan laluan 0 -> 1 -> 2 -> 4).
• Selepas pertanyaan kedua [0, 2], jalan ialah [0 -> 2, 1 -> 2 -> 3 -> 4], dan laluan terpendek dari 0 hingga 4 ialah 2 (menggunakan laluan 0 -> 2 -> 4).
• Selepas pertanyaan ketiga [0, 4], jalan ialah [0 -> 2, 1 -> 2 -> 3 -> 4], dan laluan terpendek dari 0 hingga 4 ialah 1 (jalan terus 0 -> 4).

Oleh itu, outputnya ialah [3, 2, 1].

Fikiran Akhir:

• Penyelesaian menggunakan BFS untuk setiap pertanyaan untuk mengira laluan terpendek dengan cekap.
• Graf dikemas kini secara dinamik apabila jalan baharu ditambahkan dalam setiap pertanyaan.
• Penyelesaian berfungsi dengan baik dalam kekangan masalah dan cekap mengendalikan sehingga 500 pertanyaan dengan sehingga 500 bandar.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:

• LinkedIn
• GitHub

Atas ialah kandungan terperinci Jarak Terpendek Selepas Pertanyaan Penambahan Jalan I. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!