Zadání
======

Naprogramujte zjednodušenou aplikaci IDOS. Aplikace dostane při startu jeden
argument na příkazové řádce -- název souboru s daty. Po jeho načtení přepne do
interaktivního režimu, ve kterém bude odpovídat na uživatelské dotazy. Dotazy
mají formát:

"<ze_stanice> <do_stanice> <čas_odjezdu>" -- vyhledá zadaný spoj nebo oznámí,
	že spoj není možné nalézt
"exit" -- ukončí interaktivní režim (a tedy i program)

Jména stanic odpovídají jménům načteným ze souboru a skládají se pouze z písmen
anglické abecedy a podtržítka. Názvy nejsou case-sensitive. Čas uvádíme jako
celé kladné číslo (můžete si jej představit např. jako skutečný čas převedený
na minuty od půlnoci). Jako oddělovače v dotazu může být použit libovolný počet
mezer nebo tabulátorů.

Datový soubor je textový (tj. například čísla jsou v dekadickém ASCII zápisu)
s následujícím formátem: Na prvním řádku je číslo N určující počet stanic.
Následuje N řádků, na každém je název jedné stanice. Stanice v tomto pořadí
očíslujeme (od 0 do N-1) a dále budeme používat jen číselné indexy.

Za seznamem stanic je na samostatném řádku číslo K, které udává počet vlaků.
Za ním následuje 2*K řádků se záznamy jednotlivých vlaků. Záznam vlaku se
rozkládá na dvou řádcích. První řádek obsahuje řetězec identifikující vlak
(např. "R042 Hlubina") a na druhém řádku je jízdní řád. Názvy vlaků nemusí být
unikátní (třeba proto, že jeden vlak může jet nejprve "tam" a pak "zpět").

Jízdní řád se skládá ze sudého počtu čísel, kde každá dvojice kóduje po řadě
stanici, kterou vlak projíždí, a čas, kdy ji projíždí. Pro zjednodušení
nerozlišujeme čas příjezdu a odjezdu, ale bereme pouze jeden čas jako příjezd
i odjezd. Záznamy na řádku jsou setříděny v pořadí, v jakém jimi vlak projíždí.
Vlak neprojíždí žádnou stanicí dvakrát.

V interaktivním režimu vyhledáváme vždy nejrychlejší spojení mezi nástupní a
výstupní stanicí, které odjíždí z nástupní stanice nejdříve v daný čas odjezdu.
Spojení může být i s libovolným počtem přestupů a přestupy není potřeba
minimalizovat (tj. pokud existují dva spoje se stejným časem, ale různým počtem
přesunů, stačí vypsat libovolný z nich).

Nalezený spoj vypište v libovolném čitelném formátu, tak, aby z něj byly patrné
názvy přestupních stanic, názvy použitých vlaků a všechny časy odjezdů a
příjezdů mezi přestupními stanicemi. Stanice, kterými spoj projíždí, ale
nepřestupuje se v nich, nevypisujte. Příklad:

>Liberec Klatovy 190
	R981: z Liberec do Turnov (odjezd 220, příjezd 259)
	Sp1941 Jizera: z Turnov do Praha (odjezd 281, příjezd 398)
	R962: z Praha do Klatovy (odjezd 424, příjezd 592)

Při výpočtu nijak neuvažujte, zda vlaky jezdí opakovaně (např. každý den).
Nezáleží na tom, zda si toho víc předpočítáte, nebo zda budete víc počítat při
každém dotazu. Je možné použít libovolný algoritmus s O((N*K)^2).


Algoritmický hint:
------------------
K řešení můžete použít libovolný algoritmus, nicméně pokud nevíte jak na to,
můžete použít tento:

Implementujeme variaci na Dijkstru. Budeme si pro každou stanici udržovat čas
T, kdy nejdříve se do ní umíme z počáteční dostat. Počáteční zde má dobu
zadanou od uživatele, všechny ostatní zde mají nekonečno. Všechny stanice na
začátku bereme jako "otevřené".

V každém kroku nalezneme otevřenou stanici s nejmenším T a uzavřeme ji. Při
uzavírání se podíváme na všechny odjezdy vlaků z dané stanice, s časem větším
než je T této stanice, a aktualizujeme časy T stanic, do kterých tyto vlaky
jedou (stačí aktualizovat nejbližší stanici po cestě).

Algoritmus končí v okamžiku, kdy jsme uzavřeli cílovou stanici, nebo když
uzavíráme stanici, jejíž T je nekonečno (v takovém případě cesta neexistuje).
Nezapomeňte si s časem T také udržovat, ze které stanice a jakým vlakem jste
v tento čas přijeli, aby bylo možné také zrekonstruovat výslednou cestu.


Testovací data
--------------
Seznam stanic (včetně ID):
	 0 Praha
	 1 Brno
	 2 Plzen
	 3 Ostrava
	 4 Olomouc
	 5 Ceske_Budejovice
	 6 Liberec
	 7 Hradec_Kralove
	 8 Pardubice
	 9 Prelouc
	10 Kolin
	11 Cesky_Brod
	12 Beroun
	13 Strakonice
	14 Tabor
	15 Jihlava
	16 Havlickuv_Brod
	17 Karlovy_Vary
	18 Chomutov
	19 Usti_nad_Labem
	20 Mlada_Boleslav

Seznam vlaků:
	- Praha-Český Brod-Kolín-Přelouč-Pardubicemi
		(tam i zpět, 10x po 60 min)
	- Praha-Beroun-Plzeň-Karlovy Vary
		(tam i zpět, 3x po 200 min)
	- Praha-Kolín-Pardubice-Brno
		(tam i zpět, 5x po 120 min)
	- Praha-Kolín-Havlíčkův Brod-Jihlava-Brno
		(tam i zpět 3x po 90 min)
	- Brno-Olomouc-Ostrava
		(tam i zpět 5x po 100 min)
	- Liberec-Hradec Králové-Pardubice
		(tam i zpět 3x po 250 min)
	- Liberec-Mladá Boleslav-Praha
		(tam i zpět 2x po 300 min)
	- Praha-Tábor-České Budějovice
		(tam i zpět 3x po 130 min)
	- Brno-Jihlava-České Budějovice-Strakonice-Plzeň
		(tam i zpět 2x po 180 min)
	- Plzeň-Karlovy Vary-Chomutov-Ústí nad Labem-Liberec
		(tam i zpět 2x po 210 min)
	- Pendolino Praha-Pardubice-Olomouc-Ostrava
		(tam i zpět 1x)



Příklad z aplikace:
===================

> praha kolin 0
[R 201]: praha (dep. 26) -> kolin (arr. 70)

> kolin praha 200
[Os 2102 S1]: kolin (dep. 201) -> praha (arr. 287)

> plzen ostrava 100
No connection found.

> plzen ostrava 0
[R 663]: plzen (dep. 3) -> jihlava (arr. 275)
[R 422]: jihlava (dep. 279) -> brno (arr. 320)
[Os 5210]: brno (dep. 415) -> ostrava (arr. 550)

> beroun mlada_boleslav 150
[R 758]: beroun (dep. 261) -> praha (arr. 297)
[R 315]: praha (dep. 368) -> mlada_boleslav (arr. 427)

> praha ostrava 100
[SC 513 Pendolino]: praha (dep. 126) -> ostrava (arr. 310)

> strakonice hradec_kralove 0
[R 663]: strakonice (dep. 64) -> ceske_budejovice (arr. 130)
[Sp 15113]: ceske_budejovice (dep. 174) -> praha (arr. 333)
[R 204]: praha (dep. 386) -> pardubice (arr. 459)
[R 989]: pardubice (dep. 576) -> hradec_kralove (arr. 602)

> strakonice hradec_kralove 100
No connection found.

> exit