Question
Kesultanan Bearcu sedang berperang melawan Kerajaan Macho. Salah satu mata-mata Kesultanan Bearcu berhasil mendapatkan peta logistik Kerajaan Macho, yakni sebagai berikut:
Sumber logistik Kerajaan Macho berada di node bernomor 1 dan Kerajaan Macho berada di node bernomor 9. Kesultanan Bearcu ingin memutus jalur logistik Kerajaan Macho agar memenangkan perang. Dengan kata lain, Kesultanan Bearcu ingin menghancurkan beberapa jalan sedemikian sehingga tidak ada jalan yang bisa digunakan untuk mencapai node 9 dari node 1, dan sebaliknya. Bilangan yang tertera pada jalan merupakan biaya yang dibutuhkan Kesultanan Bearcu untuk menghancurkan jalan tersebut. Berapa total biaya minimum yang dibutuhkan Kesultanan Bearcu?