Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

Jalan Tol Menuju Roma

By: a guest on Dec 21st, 2012  |  syntax: None  |  size: 2.37 KB  |  views: 42  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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.
clone this paste RAW Paste Data