Pra-OSP DKI Jakarta 2015 - Komputer, Nomor 13–14
Deskripsi Untuk Soal Nomor 13 dan 14
Gambar diatas menunjukkan peta di Kota Dengklek, pada tahun 1502. Sederhana, dan semua jalannya selalu dua arah.
13.
Berapa jarak terpendek dari kota A ke kota H?
14.
400 tahun kemudian, Gubernur baru di Kota Dengklek akan membuat jalan tol sedemikian sehingga setiap orang dapat berpergian dari dan ke kota mana saja melalui jalan tol tersebut. Berapa total panjang jalan tol minimal yang dapat dibangun?
5 jawaban
jonathan jonathan11 tahun lalu
5
14.
5 + 5 + 4 + 1 +2 +1 + 10 = 28
Nabil Ahmad11 tahun lalu
0
13. Kita dapatkan jarak terpendek adalah 14 ( A-B-G-F-H)
Fransiscus Emmanuel Bunaren9 tahun lalu
0
13. Jarak terpendek dari A -> H , bisa melalui {A => B => F =>H} senilai 14
14. (Apakah ini minimum spanning tree?)
AB+BD+BC+BG+GE+GF+FH = 28
Harso Adjie Broto S11 tahun lalu
Siswa SMA Negeri 68 Jakarta
-1
13. untuk mendapatkan nilai terkecil, kita harus menghindari nilai-nilai besar. bisa dicoba dengan metode bruteforce.
A-B-G-F-H akan menghasilkan panjang rute 5+6+2+1 14
14. karena rute A-B-G-F-H sudah menghubungkan kota A,B,G,F, dan H kita cukup mencari rute terpendek untuk menghubungkannya dengan kota lain yaitu B-D, E-G, dan B-C yang akan menghasilkan nilai 14+10+1+5 = 29
Masuk untuk menulis jawaban