Az S. 36. feladat (2008. május)

S. 36. Egy ország városait vasútvonalak kötik össze az alábbiak szerint:

-az állomásokon kívül mindenhol csak egy vágány van, a vonatok csak az állomásokon tudják kikerülni, vagy megelőzni egymást;

-a vasútvonalak csak az állomásokon találkoznak, máshol nem keresztezik egymást;

-a vasúthálózat összefüggő, azaz bármely városból bármely másik városba vezet vasútvonal vagy közvetlenül, vagy más városok érintésével;

-a vonatok mindegyike ugyanazzal a sebességgel halad bármely vasútvonalon.

Készítsünk programot, amely az ország vasúthálózata és a vonatok jelenlegi helyzete ismeretében menetrendet készít, azaz megadja, hogy mely vonatok mikor és merre haladjanak, hogy eljussanak a célállomásukra úgy, hogy az utolsóként beérkező vonat beérkezési ideje a lehető legkisebb legyen.

Az ország vasúthálózatát egy szöveges állományban adjuk meg, amelynek minden sorában két város betűjele és a városok közötti útvonal megtételéhez szükséges idő szerepel szóközzel elválasztva. Legföljebb 25 város van, az angol ABC nagybetűivel jelölve. Bármely két város közötti menetidő kisebb, mint 100 perc. A vonatok helyzetét szintén egy szövegfájlban adjuk meg, melynek soraiban elsőként annak az állomásnak a betűjele szerepel, ahol a vonat áll; a sor további betűi mind egy-egy vonatot jelölnek, melyek a betűikkel jelzett városokba szeretnének eljutni. A betűk között itt is egy szóköz az elválasztás.

A program feladata annak megadása, hogy az egyes városokból mikor és melyik útvonalon indítsuk el a vonatokat. A menetrendet egy szöveges kimeneti állományba írja a program, melynek egyes soraiban a vonat indításának perce, a vonat induló és célállomása egybe írva, valamint annak a két városnak a betűjele szerepeljen szintén egybe írva, amelyek között a vonat majd halad. A kiinduló állapotot tekintjük az időmérés kezdetének. A program írja egy másik szöveges kimeneti állományba a vonatok érkezésének idejét és az induló és célállomásuk betűjelét egybe írva. A kimeneti állományok egyes sorai legyenek az időpontok szerint növekvő sorrendben. A program négy parancssori paramétere közül az első a vasúthálózatot, a második a vonatokat tartalmazó bemeneti állományok nevei, míg a harmadik és negyedik a menetrendet és az érkezést megadó kimeneti állományok nevei.

Beküldendő a program forráskódja (s36.pas, s36.cpp, ...), valamint a program rövid dokumentációja (s36.txt, s36.pdf, ...), amely tartalmazza a megoldás vázlatos leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.

(10 pont)

A beküldési határidő 2008. június 16-án LEJÁRT.

Statisztika:

1 dolgozat érkezett.
4 pontot kapott:	1 versenyző.

A KöMaL 2008. májusi informatika feladatai