Aštuntosios baltijos šalių informatikos olimpiados uždavinių sąlygos dokumentas
5 (100%) 1 vote

Aštuntosios baltijos šalių informatikos olimpiados uždavinių sąlygos dokumentas

Aštuntosios Baltijos šalių informatikos olimpiados uždavinių sąlygos

1. Greičio limitai

(Vykdymo laikas – 2 sek.) Š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