Non-stop utazás

Dávid nem szeret az elsőbbségadás tábláknál, stoptábláknál, jelzőlámpáknál várakozni. Annak érdekében, hogy minimalizálja ezt a várakozási időt, térképet készített minden olyan régióról, amelyben gyakran utazik. Ezeken a térképeken megjelölte az általa mért átlagos várakozási időt minden útkereszteződésben. Minden régióban adott két kitüntetett pont, amelyek közt Dávid szeretné megtalálni a legrövidebb várakozási időt igénylő utat, tekintet nélkül az út távolságban mért hosszára.

Bemenet:

Az INPUT.TXT állomány tartalmazza a Dávid által készített térképek leírását. Minden régió térképének leírása a benne szereplő útkereszteződések számával (Ni) kezdődik. Egyetlen régió sem tartalmaz tíznél több útkereszteződést. A régiókon belül a kereszteződések 1-től kezdve szekvenciálisan vannak sorszámozva. Az útkereszteződések számát követő Nj sor mindegyikében egy-egy útkereszteződés specifikációja található. Minden ilyen sor a kereszteződést elhagyó utcák számával kezdődik, majd minden ilyen utcára, az utca másik végén található kereszteződés sorszámával, és az aktuális kereszteződésben a Dávid által mért átlagos várakozási idővel folytatódik. Minden régió utolsó útkereszteződésének adatai után két kereszteződés sorszáma található. Ezek közül az első annak a sorszáma, ahonnan Dávid megkezdi az útját, a második pedig annak a sorszáma, ahol befejezi. A teljes inputot — mely a régiók leírásának sorozatából áll — egyetlen 0 zárja.

Kimenet:

Írjuk az eredményeket az OUTPUT.TXT nevű állományba! Minden régióhoz egyetlen sor tartozik. Ez tartalmazza a legrövidebb várakozási időt igénylő úton szereplő kereszteződések sorszámait, valamint a minimális várakozási időt. A példa egy alkalmas formátumot mutat, de más output formátum is elfogadható.

Megjegyzések:

1. Minden régióban egyetlen minimális várakozási időt igénylő út van
2. Az átkereszteződések közti utcák egyirányúak. Az i és j útkereszteződések közti kétirányú utca reprezentálásához az input tartalmaz (i,j) és (j,i) utcát is.
3. Bármely i és j útkereszteződések közt legfeljebb egy utca lehetséges.

Példa:

INPUT.TXT

OUTPUT.TXT

5
2 3 3 4 6
3 1 2 3 7 5 6
1 4 5
0
1 4 7
2 4
2
1 2 5
1 1 6
1 2
0

Teszt#1: Útvonal: 2 1 4 Várakozási idő: 8
Teszt#2: Útvonal: 1 2 Várakozási idő: 5

 

 

 

 

 

 

 

 

 

 

 

 

(ACM regionális verseny 1995)