Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_2000_3e2_aplink_zeme_vyr.in

Rezultatų failas: lmio_2000_3e2_aplink_zeme_vyr.out

Jei norite pateikti savo sprendimą - prisijunkite.

Aplink žemę per 80 dienų

Ž. Verno knygoje pasakojama, kaip Filijas Fogas apkeliavo aplink Žemę per 80 dienų. Tačiau gal būt sudarius labai gerą maršrutą, jam būtų pasisekę apkeliauti dar greičiau.

Žinomi įvairių transporto priemonių (traukinių, keltų ir t. t.) tvarkaraščiai. Visomis dienomis tvarkaraščiai yra tokie patys. Apie kiekvieną reisą žinoma šitokia informacija: išvykimo miestas, išvykimo laikas, miestai, kuriuose stojama, kelionės laikas tarp gretimų stočių. Visi tvarkaraščiai nurodyti Grinvičo laiku.

Keliaujama tik į rytus, todėl visą kelionės laiką naudojamasi tik rytų kryptimi vykstančių transporto priemonių tvarkaraščius.

Persėsti iš vienos transporto priemonės į kitą (pvz., iš vieno traukinio į kitą) reikia bent penkių minučių, todėl jei, pavyzdžiui, išlipama stotyje 13:03, tai iš jos išvykti galima anksčiausiai 13:08. Laikoma, kad tarpinėje stotyje transporto priemonės atvyksta ir išvyksta tą pačią minutę.

Užduotis

Žinomas miestas, kuriame gyvena F. Fogas. Kelionės pradžia lygiai vidurnaktis Grinvičo laiku. Parašykite programą, kuri nustatytų, ar galima apkeliauti aplink Žemės rutulį pagal pateiktus susisiekimo priemonių tvarkaraščius ir, jei galima, praneštų, kada anksčiausiai įmanoma grįžti namo (t. y. į miestą, iš kurio buvo išvykta).

Pradiniai duomenys

Pirmoje eilutėje įrašytas miestų skaičius M, pradinis miestas P, reisų skaičius R. Laikoma, kad miestai sunumeruoti nuo 1 iki M, reisai – nuo 1 iki R.

Kitose eilutėse surašyti reisų tvarkaraščiai. Vienam reisui skirtos kelios eilutės. Pirmoje eilutėje nurodytas išvykimo miesto numeris nr. Paskui – išvykimo laikas: valandos h ir minutės min, tarpinių ir galutinės stočių bendras skaičius ts. Kiekvienoje iš tolesnių t seilučių pateikta informacija apie vieną tarpinę (ar galutinę) stotį: miestas a, į kurį atvykstama, ir kelionės trukmė nuo prieš tai buvusios stoties, t.y. valandos th ir minutės min.

Taigi, vienam reisui skiriama ts+1 eilutė.

Rezultatai

Rezultatai įrašomi į pirmąją eilutę. Jei apkeliauti aplink Žemę neįmanoma, tai rašomas žodis NEGALIMA. Priešingu atveju įrašomas trumpiausias laikas, kuris reikalingas sugrįžti namo, t. y. parų, valandų ir minučių skaičius.

Pavyzdžiai

Pradiniai duomenys Rezultatai Paaiškinimas
#5 3 3 3 0 0 3 1 8 19 4 21 7 5 7 18 1 8 23 1 3 16 23 5 6 23 2 3 18 12 2 17 32# 
2 0 46
 
Kelionė užtruks 2 paras ir 46 minutes. Iš trečio miesto išvykstama pirmu reisu 5:35 val. ir atvykstama į pirmą miestą po 2 valandų ir 44 minučių, t. y. 8:19 val.. Persėstiįkitątransportopriemonęnespėjama, todėl tenka laukti kito ryto ir 8:23val antru reisu vykstama iki trečio miesto. Kelyje sugaištama 16 valandų ir 23 minutes. Visa kelionė trunka 2 paras ir 46 minutes.

Ribojimai

2\\leqM\\leq500

1\\leqP\\leqM

1\\leqR\\leq200

1\\leqnr\\leqM

0\\leqh\\leq23

0\\leqmin\\leq59

1\\leqts\\leq150

1\\leqa\\leqM

0\\leqth\\leq10000