API tools faq
paste
Guest User

Jalan Tol Menuju Roma

a guest
Dec 21st, 2012
59
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.37 KB | None | 0 0
raw download clone embed print report
  1. Jalan Tol Menuju Roma
  2.  
  3. Batas Waktu 1 detik
  4. Batas Memori 16 MB
  5. Seorang pengelana yang mengendarai mobil berada di sebuah kota, dan ingin menuju kota Roma. Di negara Italia, ada N (1 ≤ N ≤ 500) buah kota, dan kota-kota ini dihubungkan oleh L buah ruas jalan (1 ≤ L ≤ 125000), di mana sebuah ruas jalan menghubungkan dua kota yang berbeda. Selain itu, ada juga T (1 ≤ T ≤ 125000) buah ruas jalan tol, di mana sebuah ruas jalan tol menghubungkan dua kota yang berbeda. Setiap pasang kota dapat dihubungkan hanya oleh sebuah ruas jalan biasa, atau hanya oleh sebuah ruas jalan tol, atau tidak dihubungkan oleh ruas jalan.
  6.  
  7. Sang pengelana ingin mencapai kota Roma dalam waktu yang secepat-cepatnya. Sang pengelana tahu bahwa sebuah ruas jalan biasa atau jalan tol dapat ditempuh dalam waktu 1 jam. Namun, sang pengelana hanya memiliki satu buah tiket jalan tol, yang hanya dapat digunakan untuk melintasi satu ruas jalan tol saja. Selebihnya, sang pengelana harus menggunakan jalan biasa. Sang pengelana juga boleh saja untuk tidak memakai tiket jalan tolnya, jika dia dapat mencapai kota Roma dalam waktu yang secepat-cepatnya.
  8.  
  9. Buatlah program yang dapat mengeluarkan banyak jam paling sedikit untuk mencapai kota Roma dari kota asal.
  10.  
  11. Format Masukan
  12.  
  13. Baris pertama berisi lima buah bilangan bulat, masing-masing dipisahkan oleh sebuah spasi: N, L, T, nomor kota awal, dan nomor kota Roma. Kota-kota dinomori 1 sampai dengan N.
  14.  
  15. L baris berikutnya masing-masing mendeskripsikan sebuah ruas jalan. Setiap baris terdiri atas dua buah kota, yaitu nomor kedua kota yang dihubungkan oleh ruas jalan tersebut.
  16.  
  17. T baris berikutnya masing-masing mendeskripsikan sebuah ruas jalan tol. Setiap baris terdiri atas dua buah kota, yaitu nomor kedua kota yang dihubungkan oleh ruas jalan tol tersebut.
  18.  
  19. Format Keluaran
  20.  
  21. Baris pertama berisi sebuah bilangan bulat, yaitu banyak jam paling sedikit untuk mencapai kota Roma dari kota asal, dengan atau tanpa menggunakan satu-satunya tiket jalan tol. Dijamin pasti ada rute dari kota asal ke kota Roma.
  22.  
  23. Contoh Masukan
  24.  
  25. 7 9 2 1 7
  26. 1 2
  27. 1 3
  28. 3 2
  29. 2 4
  30. 4 3
  31. 4 5
  32. 4 6
  33. 5 7
  34. 6 7
  35. 3 6
  36. 5 6
  37. Contoh Keluaran
  38.  
  39. 3
  40. Penjelasan
  41.  
  42. Contoh masukan dapat diilustrasikan dengan gambar di bawah ini. Ruas garis berwarna biru berarti jalan tol. Rute tercepat adalah dari 1 ke 3 ke 6 ke 7.
  43.  
  44.  
  45. Tips
  46.  
  47. Coba pikirkan apakah yang disebut sebuah state dalam masalah pencarian ini.
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!