Mentők

Adva van egy város, amelyben több mentőállomás és kórház működik. Riasztás esetén a diszpécser értesíti a riasztás helyszínéhez legközelebb eső mentőállomást, megad egy lehetséges legrövidebb útvonalat az állomástól a helyszínig, és megad egy legrövidebb útvonalat a helyszíntől a legközelebbi kórházig. Írjunk programot, amely meghatározza ezeket a legrövidebb útvonalakat!

Bemenet:

Adva van a város térképe. A térképen az útkereszteződések, a mentőállomások és a kórházak egy-egy nem negatív egész számmal vannak azonosítva, ezek egyike sem nagyobb 999-nél. Az útszakaszokat egy számhármas adja meg. A számhármas első két tagja egy-egy "szomszédos" útkereszteződés, mentőállomás vagy kórház azonosítója, a harmadik tag az útszakasz méterben megadott hossza. Egy útszakaszon a mentőautó mindkét irányba közlekedhet.

Az INPUT.TXT állomány első sorában szerepelő N egész szám (0<N<100000) megadja a térképen szereplő útszakaszok számát. A következő N sor tartalmazza a már említett útszakaszok leírására szolgáló számhármasokat.

Ezt követi egy egész szám (0<m<100), amely megadja a mentőállomások számát. A következő m egész szám a mentőállomások azonosítóit tartalmazzák. Ezt követi egy egész szám (0<k<100), amely megadja a kórházak számát. A következő k egész szám a kórházak azonosítóit tartalmazzák. Eddig a város topológiájának adatait adtuk meg. Ezután következnek a kérések. Minden kérés a riasztáshoz legközelebbi útkereszteződés azonosítóját tartalmazza. Az input végét egy -1-es szám jelzi.

Feltételezhetjük, hogy a mentőállomásokon mindig van szabad mentőautó, és az input állományban megadott kórházak, korlátlan mennyiségű beteget fogadhatnak.

Kimenet:

Minden kérésre adjuk meg a legrövidebb útvonal hosszát, majd az egyik legrövidebb útvonalat a mentőállomás és a riasztáshoz legközelebbi útkereszteződés ill. a kórház között, a mentőállomás, az útkereszteződések és a kórház azonosítójának vesszővel elválasztott felsorolásával. Amennyiben egyetlen mentőállomásról sem érhető el a riasztás helyszíne ill. egyetlen kórház sem elérhető a riasztás helyszínéről, írjuk ki, hogy "Helikopteres intezkedes szukseges!". Az egyes válaszok között hagyjunk ki egy üres sort.

Példa:

INPUT

OUTPUT

4

1      2       1

2      3       1

3      4       1

4      1       1

1      1

1      2

3

1

2

-1

2 : (1,2,3)

1 : (3,2)

 

0 : (1)

1 : (1,2)

 

1 : (1,2)

0 : (2)

 

Tesztadatok:

 

i31_1

i31_2

i31_3

i31_4

i31_5

i31_6

i31_7

 

i31_3 tesztadatsor eredmény:mo_3.txt

i31_7 tesztadatsor eredmény:mo_7.txt

 

(Nagy Tibor)