B - Lístok na vlak

Časový limit: 3s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Dr. Cooper dnes cestuje vlakom na druhý koniec Slovenska. Ako si tak krátil čas čakaním na vlak, všimol si nasledujúci cenník. "Hmm, zaujímavé", povedal si dr. Cooper po chvíli štúdia. Podľa tohto cenníka je totižto často výhodnejšie si namiesto priameho lístka kúpiť niekoľko lístkov na kratšie trate. Napríklad, priamy lístok Košice-Sp.Nová Ves stojí 112Sk, zatiaľ čo lístky Košice-Margecany (48Sk) a Margecany-Sp.Nová Ves (42Sk) stoja dohromady len 90Sk. Dr. Cooper by sa teraz s týmto objavom rád podelil so spolucestujúcimi vo vlaku. Pomôžte mu určiť minimálnu cenu medzi dvoma zastávkami jeho vlaku (uvažujeme 2. triedu s celým lístkom).

Úloha

Dané je rozmiestnenie zastávok vlaku v ktorom sedí dr. Cooper. Napíšte program, ktorý pre dané dve zastávky určí minimálnu cenu cestovného.

Vstup

Prvý riadok obsahuje kladné celé číslo N (2≤N≤100). Nasledujúcich N riadkov popisuje zastávky vlakov, v ktorom sedí dr. Cooper. Každý riadok popisujúci zastávku vlaku obsahuje kladné celé číslo určujúce vzdialenosť zastávky od východzej stanice a medzerou oddelený názov zastávky. Ďalej vstup obsahuje kladné celé číslo Q (2≤Q≤1000), určujúce počet cestujúcich, ktorých dr. Cook vo vlaku stretol. Každá z nasledujúcich dvojíc riadkov určuje názov nástupnej resp. cieľovej stanice. Môžete predpokladať, že vlak necestuje viac ako 1 000 kilometrov a názov každej stanice obsahuje najviac 50 znakov.

Výstup

Pre každého cestujúceho zo vstupu vypíšte minimálnu cenu, ktorú musí zaplatiť na danej trase. Výstup má dokopy obsahovať Q čísel, každé v samostatnom riadku.

Príklad

Vstup:

20
0 Kosice
16 Kysak
35 Margecany
75 Spisska Nova Ves
101 Poprad-Tatry
120 Strba
159 Liptovsky Mikulas
242 Zilina
259 Bytca
274 Povazska Bystrica
286 Puchov    
301 Ilava
313 Trencianska Tepla
321 Trencin
346 Nove Mesto nad Vahom
364 Piestany
382 Leopoldov
399 Trnava
441 Bratislava-Vinohrady
445 Bratislava hl.st.
3
Kosice
Spisska Nova Ves
Zilina
Trencin
Kosice
Bratislava hl.st.

Výstup:

90
100
518

06 Domáce