Greičio ribojimai

Šiuolaikiniame pasaulyje, dažniausiai renkamės ne trumpiausią kelią, o kelią, kuriame užtrunkame mažiausiai laiko. Taigi, važiuojant automobiliu, greičio ribojimai yra svarbūs. Įsivaizduokite, kad kai kurie greičio ribojimo ženklai keliuose paslaptingai dingo. Kadangi negalima tikėtis iš vairuotojo, kad jis viską prisimins, peršasi vienintelė logiška išvada: pravažiavęs vietą, kur anksčiau buvo kelio ženklas, vairuotojas laikysis to paties greičio ribojimo, kokio jis laikėsi prieš atvažiuodamas į tą vietą. 

Duotas kelių tinklo aprašas. Paprastumo dėlei laikykite, kad kelių tinklas susideda iš kelių ir sankryžų. Visi keliai yra vienpusiai, jungia lygiai dvi sankryžas ir juose yra ne daugiau vieno greičio ribojimo ženklo, kuris yra (jei yra) pačioje kelio pradžioje. Iš sankryžos A į sankryžą B gali eiti ne daugiau kaip vienas kelias. Laikykite, kad greitis pakinta akimirksniu ir nėra jokių kitų veiksnių, kurie gali daryti įtaką Jūsų kelionei. Ir, žinoma, jokiu būdu negalima važiuoti greičiau, negu leidžia paskutinysis Jūsų pravažiuotas ženklas.

UŽDUOTIS
Parašykite programą, kuri surastų mažiausiai laiko reikalaujantį maršrutą, pasinaudodama tuo, kad kai kurie ženklai yra dingę. 

PRADINIAI DUOMENYS
Pradiniai duomenys įrašyti byloje speed.in. Pirmoje eilutėje yra trys sveikieji skaičiai N, M ir D. Čia N (2£N£150) – sankryžų skaičius. Jos numeruojamos nuo 0 iki N – 1. M yra kelių skaičius, o D žymi sankryžą, į kurią Jums reikia patekti iš nulinės sankryžos. 

Kiekvienoje tolesnių M eilučių aprašytas vienas kelias. Kelią aprašanti eilutė sudaryta iš keturių sveikųjų skaičių A (0£A<N), B (0£B<N), V (0£V£500) ir L (1£L£500). Jie reiškia, kad kelias tęsiasi iš sankryžos A į sankryžą B, greičio ribojimas kelyje – V, o kelio ilgis yra L. 

Jei V lygus nuliui, tai greičio ribojimo ženklas šiame kelyje yra dingęs. Kelyje sugaištas laikas T apskaičiuojamas pagal formulę T = L/V, jei V ¹ 0, priešingu atveju T = L/Vsen, kur Vsen yra greičio ribojimas, kurio laikėtės iki tol, kol atvažiavote į šią sankryžą. 

Atkreipiame dėmesį, kad operacijos turėtų būti atliekamos su slankaus kablelio skaičiais, kad būtų išvengta nereikalingo apvalinimo. 

Pradiniu momentu esate sankryžoje 0 ir laikotės 70 vienetų greičio ribojimo.

REZULTATAI
Rezultatų bylą speed.out turi sudaryti viena eilutė. Joje reikia išvardinti sankryžas, per kurias reikia važiuoti, norint kelyje iš sankryžos 0 į sankryžą D sugaišti mažiausiai laiko. Sankryžos turi būti surašytos tiksliai tokia tvarka, kokia per jas yra važiuojama. Taigi pirmoji sankryža turėtų būti 0, o paskutinioji – D. 

Pradiniai duomenys tokie, kad kelias, kuriame užtrunkama trumpiausiai, bus tik vienas.

PRADINIŲ DUOMENŲ IR REZULTATŲ PAVYZDŽIAI

Pradiniai duomenys 		Rezultatai 		Paaiškinimas
(speed.in)		(speed.out)

Kelionėje sugaištas laikas šiuo atveju yra lygus 2,628.

0 5 2 3 1

6 15 1
0 1 25 68
0 2 30 50
0 5 0 101
1 2 70 77
1 3 35 42
2 0 0 22
2 1 40 86
2 3 0 23
2 4 45 40
3 1 64 14
3 5 0 23
4 1 95 8
5 1 0 84
5 2 90 64
5 3 36 40