Az évfolyam kirándulását tervezi. Az A városból indulnak és a B város a cél. Az útvonal megtervezéséhez van olyan menetrendjük, amely tartalmazza, hogy mely városok között van közvetlen buszjárat (mindkét irányban). Bizonyos városokat célszerű elkerülni, mert útépítések miatt hosszadalmas áthaladni rajtuk. Ismerik ezeket az elkerülendő városokat is.
FeladatÍrj programot, amely kiszámít egy olyan A-ból B-be vezető útvonalat, amely a lehető legkevesebb elkerülendő várost tartalmazza!
BemenetA standard bemenet első sorában a városok N száma (1<=N<=10000), a városok közötti közvetlen buszjáratok M száma (1<=M<=200000) és az elkerülendő városok K száma (1<=K<=N) van. A második sor az indulási város A és a cél város B sorszámát tartalmazza. A harmadik sor pontosan K számot tartalmaz, az elkerülendő városok sorszámát. A további M sor mindegyike egy közvetlen kétirányú buszjárattal összekötött két város sorszámát tartalmazza (1 <= u ≠ v <=N). Tudjuk, hogy biztosan van legalább egy útvonal A-ból B-be.
KimenetA standard kimenet első sora első száma a legkevesebb elkerülendő várost tartalmazó A-ból B-be vezető útvonal városainak R száma (beleértve az indulási és érkezési várost is), a második pedig az útvonalba eső elkerülendő városok S száma legyen! A második sor pontosan R számot tartalmazzon, az út során érintett városok sorszámát az utazás sorrendjében! Több megoldás esetén bármelyik megadható.
Példa
 Tesztadatok
CímkékA feladat forrása: biro.inf.elte.hu/Mester
Algoritmusok: legrövidebb utak, szélességi bejárás, prioritási sor
megoldás |
Programozás > Feladatok >
