- Nosaukums
- Sliedes un pārmijas (tram)
- Laika limits
- 1.00s
- Atmiņas limits
- 256.0 MB
- Grūtība
-
86%
Definīcija
Tramvaju sliežu tīkls sastāv no sliežu posmiem un N krustojumiem. Krustojumi ir numurēti ar naturāliem skaitļiem no 1 līdz N pēc kārtas. Noteiktus krustojumus savieno sliežu posmi. Katrā krustojumā ir pārmija, kas ir pārslēgta uz vienu izejošo sliežu posmu. Ja tramvajs iebrauc krustojumā, tas no krustojuma var izbraukt tikai pa to sliežu posmu, uz kuru ir pārslēgta pārmija. Ja tramvajam nepieciešams braukt pa citu sliežu posmu, tad vadītājam pārmija ir jāpārslēdz. Ar vienu pārmijas pārslēgšanu vadītājs var pārslēgt pārmiju uz jebkuru no izejošajiem sliežu posmiem.
Ja tramvaja vadītājam ir jāaizbrauc no krustojuma A līdz krustojumam B, tad viņš cenšas atrast tādu maršrutu, kurā pārmiju pārslēgšanu skaits būtu mazākais iespējamais.
Uzrakstiet programmu, kas dotiem krustojumiem atrod mazāko nepieciešamo pārmiju pārslēgšanu skaitu maršrutā no viena krustojuma līdz otram!
Ievaddatu raksturojums
Ievaddatu pirmajā rindā dotas trīs naturālu skaitļu N(krustojumu skaits, 2 ≤N≤100), A un B(krustojumu - maršruta galapunktu numuri, 1≤A,B≤N) vērtības, kas atdalītas ar tukšumsimboliem.
Katra no nākošajām N ievaddatu rindām satur veselu skaitļu virkni, kur blakus skaitļus atdala tukšumsimboli. Pirmais skaitlis i-tajā rindā Ki(0≤Ki≤N-1) ir sliežu posmu skaits, kas iziet no i-tā krustojuma. Nākošie Ki skaitļi apzīmē to krustojumu numurus uz kuriem iet šie sliežu posmi. Sākotnēji katra pārmija ir pārslēgta uz pirmo no izejošajiem sliežu posmiem.
Izvaddatu raksturojums
Izvaddatu vienīgajā rindā jāizvada vesels skaitlis - mazākais nepieciešamais pārmiju pārslēgšanu skaits. Ja no krustojuma A līdz krustojumam B aizbraukt nav iespējams, jāizvada skaitlis '-1'.
Piezīmes
Uzdevums izmantots Horvātijas informātikas olimpiādē 2002.gadā
Paraugdati
Stdin
3 2 1 2 2 3 2 3 1 2 1 2
Stdout
0
Stdin
3 1 3 1 2 2 1 3 1 2
Stdout
1
Stdin
4 4 2 1 2 1 1 1 4 1 3
Stdout
-1
Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.