Rute Terpendek Antarkota
Cari jarak tempuh terpendek antara dua kota dengan algoritma Dijkstra.
Aplikasi peta di ponselmu menghitung rute tercepat dalam sekejap, padahal jalannya jutaan. Salah satu algoritma di baliknya ditemukan Edsger Dijkstra pada 1956. Kali ini kamu yang menulisnya.
Masukan
Baris pertama berisi N (2 sampai 5000) banyaknya kota dan M (1 sampai 20000) banyaknya jalan. M baris berikutnya berisi A B W, jalan dua arah antara kota A dan B sepanjang W kilometer (1 sampai 1000). Baris terakhir berisi kota asal S dan kota tujuan T.
Keluaran
Jarak terpendek dari S ke T, atau Tidak terhubung bila tidak ada jalan sama sekali.
Contoh masukan dan keluaran
Contoh 1
Masukan
5 6 1 2 7 1 3 3 3 2 2 2 4 4 3 4 8 4 5 1 1 5
Keluaran
10
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Simpan jarak sementara setiap kota, awalnya tak hingga kecuali kota asal. Selalu proses kota dengan jarak sementara terkecil yang belum selesai.
Petunjuk 2
Pakai heap supaya kota terdekat berikutnya bisa diambil dengan cepat. Saat memproses sebuah kota, coba perbaiki jarak setiap tetangganya.