Closed stevenwjy closed 6 years ago
Negative cycle pasti bisa dikunjungi dari awal, karena bellman ford-nya dilakukan dengan node awal berupa posisi awal Pak Dengklek.
Mungkin masalahnya adalah kalau negative cycle tidak bisa mencapai node akhir?
Dalam kasus ini, tetap output Pak Dengklek tidak mau pulang
karena syaratnya:
"Hal ini terjadi ketika ada suatu rangkaian ruas jalan sehingga Pak Dengklek tidak mungkin kehabisan energi bila terus berputar-putar di rangkaian tersebut."
Jadi tidak harus menuju node akhir
Iya, node awalnya kan posisi Pak Dengklek dan distance nya jadi 0, namun sebelum menjalankan bellman ford, tidak dilakukan pengecekan dulu apakah distancenya masih INF (atau belum bisa dikunjungi dari posisi awal).
Contohnya yaitu pada tc ini :
5 4 0 4 -3 1 2 -1 2 3 -1 3 1 -1
Pada solusi saya yang AC mengoutputkan jawaban kalau pak dengklek tidak mau pulang, padahal seharusnya tidak bisa mengunjungi negative cycle tersebut.
@stevenwjy oh begitu.. oke sekarang uda diperbaiki. Bisa coba submit solusi benernya buat verifikasi?
@gyosh sudah saya coba submit kak dan sekarang sudah AC solusi yang sebelumnya WA 80. Thank you kak.
baiklah makasih ya buat laporan bugnya!
Testcase bermasalah karena solusi juri tidak melakukan pengecekan terlebih dahulu jika ada negative cycle yakni apakah bisa dikunjungi dari posisi awal.