Olimpiade Sains Kota (OSK) 2022 - Komputer, Nomor 6

Diketahui 8 buah kota dengan label 0, 1, 2, ..., 7 yang masing-masing terhubung dengan sebuah jalan. Setiap jalan bersifat satu arah.

Diketahui pula waktu tempuh dari satu kota ke kota yang lain melalui masing-masing jalan sesuai dengan nilai yang ditunjukkan pada masing-masing jalur penghubung (dalam satuan jam). Waktu tempuh antara dua buah kota didefinisikan sebagai nilai terkecil dari total waktu tempuh jalan-jalan yang harus dilewati untuk berpindah dari satu kota ke kota lainnya. Misalnya, waktu tempuh dari 2 ke 7 adalah 3, karena kita dapat melalui jalur 2→3 (waktu tempuh = 2) dan jalur 3→7 (waktu tempuh = 1), sehingga total = 2 + 1 = 3, dan tidak ada jalur lain dari 2 ke 7 yang memiliki total waktu tempuh < 3. Kota manakah yang waktu tempuhnya dari 0 paling besar?

1. 3

2. 4

3. 5

4. 6

5. 7