Ubah suai Pemberat Tepi Graf

2699. Ubah suai Berat Tepi Graf

Kesukaran:Sukar

Topik:Graf, Timbunan (Baris Gilir Keutamaan), Laluan Terpendek

Anda diberi grafberwajaran tidak terarah disambungkanyang mengandungi n nod berlabel dari 0 hingga n - 1 dan tepi tatasusunan integer dengan tepi[i] = [a_i, b_i, w_i] menunjukkan bahawa terdapat tepi antara nod a_idan b_idengan berat w_i.

Sesetengah sisi mempunyai berat -1 (w_i= -1), manakala yang lain mempunyai beratpositif(w_i> 0) .

Tugas anda ialah mengubah suaisemua tepidengan berat -1 dengan memberikannyanilai integer positifdalam julat [1, 2 * 10⁹] supayajarak terpendekantara sumber nod dan destinasi menjadi sama dengan sasaran integer. Jika terdapatpelbagai pengubahsuaianyang menjadikan jarak terpendek antara sumber dan destinasi sama dengan sasaran, mana-mana daripadanya akan dianggap betul.

Kembalikantatasusunan yang mengandungi semua tepi (walaupun yang tidak diubah suai) dalam sebarang susunan jika mungkin untuk menjadikan jarak terpendek dari sumber ke destinasi sama dengan sasaran, atautatasusunan kosongjika mustahil.

Nota:Anda tidak dibenarkan mengubah suai pemberat tepi dengan pemberat positif awal.

Contoh 1:

• Input:n = 5, tepi = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1] ], sumber = 0, destinasi = 1, sasaran = 5
• Output:[[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
• Penjelasan:Graf di atas menunjukkan kemungkinan pengubahsuaian pada tepi, menjadikan jarak dari 0 hingga 1 sama dengan 5.

Contoh 2:

• Input:n = 3, tepi = [[0,1,-1],[0,2,5]], sumber = 0, destinasi = 2, sasaran = 6
• Output:[]
• Penjelasan:Graf di atas mengandungi tepi awal. Tidak mungkin untuk membuat jarak dari 0 hingga 2 sama dengan 6 dengan mengubah suai tepi dengan berat -1. Jadi, tatasusunan kosong dikembalikan.

Contoh 3:

• Input:n = 4, tepi = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], sumber = 0, destinasi = 2, sasaran = 6
• Output:[[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
• Penjelasan:Graf di atas menunjukkan graf diubah suai yang mempunyai jarak terpendek dari 0 hingga 2 sebagai 6.

Kekangan:

• 1 <= n <= 100
• 1 <= tepi.panjang <= n * (n - 1) / 2
• tepi[i].panjang == 3
• 0 <= a_i, b_i< n
• w_i= -1 atau 1 <= w_i<= 10⁷
• a_i!= b_i
• 0 <= sumber, destinasi < n
• sumber != destinasi
• 1 <= sasaran <= 10⁹
• Graf disambungkan dan tiada gelung kendiri atau tepi berulang

Petunjuk:

1. Pertama sekali, semak sama ada anda boleh membuat laluan terpendek dari sumber ke destinasi sama dengan sasaran.
2. Jika laluan terpendek dari sumber ke destinasi tanpa tepi untuk diubah suai, adalah kurang daripada sasaran, maka ia tidak boleh dilakukan.
3. Jika laluan terpendek dari sumber ke destinasi termasuk tepi yang akan diubah suai dan memberikan mereka berat sementara 1, adalah lebih besar daripada sasaran, maka ia juga tidak mungkin.
4. Andaikan kita boleh mencari tepi boleh diubah suai (u, v) supaya panjang laluan terpendek dari sumber ke u (dis1) ditambah panjang laluan terpendek dari v ke destinasi (dis2) adalah kurang daripada sasaran (dis1 + dis2 < target), maka kita boleh menukar beratnya kepada “target - dis1 - dis2”.
5. Untuk semua sisi lain yang masih mempunyai berat "-1", tukar pemberat kepada nombor besar yang mencukupi (sasaran, sasaran + 1 atau 200000000 dll.).

Penyelesaian:

Kita boleh memecahkan pendekatan seperti berikut:

Pendekatan:

1. Semakan Awal dengan Berat Sedia Ada:

   • Mula-mula, kami mengira laluan terpendek dari sumber ke destinasi menggunakan hanya tepi dengan pemberat positif, mengabaikan tepi dengan berat -1.
   • Jika jarak ini sudah lebih besar daripada sasaran, maka adalah mustahil untuk mengubah suai -1 tepi untuk mencapai sasaran, jadi kami mengembalikan tatasusunan kosong.

2. Tugas Sementara Berat 1:

   • Seterusnya, tetapkan berat sementara 1 pada semua tepi dengan berat -1 dan kira semula laluan terpendek.
   • Jika laluan terpendek ini masih lebih besar daripada sasaran, maka adalah mustahil untuk mencapai sasaran, jadi kami mengembalikan tatasusunan kosong.

3. Ubah suai Berat Tepi Tertentu:

   • Lelaran melalui tepi dengan berat -1 dan kenal pasti tepi yang boleh dilaraskan agar sepadan dengan jarak sasaran. Ini dilakukan dengan melaraskan berat tepi supaya gabungan jarak laluan menuju dan dari tepi ini menghasilkan jarak sasaran yang tepat.
   • Untuk mana-mana baki -1 tepi, tetapkan berat yang cukup besar (cth., 2 * 10^9) untuk memastikan ia tidak menjejaskan laluan terpendek.

4. Kembalikan Tepi Ubah Suai:

   • Akhir sekali, kembalikan senarai tepi yang diubah suai.

Mari laksanakan penyelesaian ini dalam PHP:2699. Ubah suai Pemberat Tepi Graf

        
Penjelasan:
        

         
Fungsi dijkstra mengira laluan terpendek dari sumber ke semua nod lain.
         
Kami pada mulanya mengira laluan terpendek tanpa menghiraukan -1 tepi.
         
Jika laluan tanpa -1 tepi kurang daripada sasaran, fungsi mengembalikan tatasusunan kosong, menunjukkan mustahil untuk melaraskan pemberat untuk memenuhi sasaran.
         
Jika tidak, kami tetapkan semua -1 tepi kepada 1 buat sementara waktu dan semak sama ada laluan terpendek melebihi sasaran.
         
Jika ia berlaku, sekali lagi mustahil untuk mencapai sasaran, dan kami mengembalikan tatasusunan kosong.
         
Kami kemudian mengubah suai pemberat -1 tepi secara strategik untuk mencapai laluan terpendek yang diingini tepat sasaran.
        
Pendekatan ini memeriksa dan melaraskan pemberat tepi dengan cekap, memastikan jarak sasaran dicapai jika boleh.
Pautan Kenalan
Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberirepositoribintang 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 Ubah suai Pemberat Tepi Graf. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!