Olimpiade Sains Provinsi (OSP) 2017 - Komputer, Nomor 30
Anab lngln mengunjungi Jauhar. la harus melalui jalan-jalan searah yang dipenuhi monster. Anab memerlukan energi untuk melawan monster-monster tersebut. Anab akan kehilangan energi sebesar N untuk mengalahkan N monster. Setiap persimpangan jalan dijaga oleh Kingkong berkekuatan X sehingga Anab memerlukan energi minimal sebesar X untuk mengalahkan KingKong (jika energinya habis maka Anab akan mati). Anab ingin agar saat berjumpa dengan Jauhar, tenaganya masih tersisa sebesar mungkin. Peta jalan yang harus ditempuh Anas
dinyatakan dalam gambar berikut:
Jika tenaga awal Anab adalah 3000, berapakah tenaga maksimal yang masih dapat dimiliki Anab ketika sampai di tempat Jauhar?
4 jawaban
Muhammad Fairuzi Teguh8 tahun lalu
0
Soal ini merupakan salah satu contoh soal algoritma Dijkstra.
Setelah menggunakan algoritma dijkstra, dapat dilihat bahwa sisa energi maksimal adalah 1857 dengan rute sebagai berikut (ditandai dengan no kingkong):
Anab -> 30 -> 40 -> 50 -> 100 -> 30 -> 10 -> 1 -> Jauhar
Muhammad Fairuzi Teguh8 tahun lalu
yang dihitung justru edgenya
Salsabila .8 tahun lalu
SMAIT Nur Hidayah
banyaknya kingkong yang ada di garis enggak masuk ke hitungan ya?
Muhammad Fairuzi Teguh8 tahun lalu
Yang di node (persimpangan) adalah kekuatan kingkong, bukan banyak kingkong. Dari soal, kita hanya perlu memiliki energi minimal X untuk mengalahkan kingkong dan tidak ada penjelasan bahwa energi kita akan berkurang sebanyak X.
Joel Gunawan5 tahun lalu
bknnya bisa langsung ke 50 ya?
Joel Gunawan5 tahun lalu
gw dpt cara paling efisien 50 -> 9 -> 10 -> Jauhar jadinya 3000-50-9-10=3000-69=2931
Masuk untuk menulis jawaban
edgenya gak dihitung?