NézetNyomtat

Indiana Jones (Megoldás)
Versenyek > ACM
Címkék > Feladat
Elmélet > Algoritmusok > Gráfalgoritmusok

Indiana Jones

Indiana Jones egy elhagyott romvárosban jár. A háztetők mind megsemmisültek egy háborúban, a falak egy része még áll. Rengeteg akna van elásva a földben, ezért csak a megmaradt falszakaszokon biztonságos járni. Indiana Jonesnak meg kell mentenie egy embert, aki csapdába esett a városban. Két falszakasz között egy falétra segítségével lehet átmenni, ha elég hosszú a létra ahhoz, hogy átérjen a két falszakasz között.
A falszakaszok kelet-nyugati vagy észak-déli irányúak, Indiana Jones és a csapdába esett ember kezdetben egy-egy falszakasz tetején van.

Feladat

Az ősi város maradványainak térképét ismerjük, és ki kell számítanunk a legrövidebb létra hosszát, amivel a küldetés végrehajtható.

Bemenet

Az indiana.be állomány több tesztesetet tartalmaz. Minden teszteset az falszakaszok $N$ számával kezdődik. ($2\le N \le 1000$) A következő $N$ sor a falszakaszokat adja meg. Az első az, ahol Indiana Jones van kezdetben, a második pedig az, ahol a megmentendő ember várakozik. Minden falszakaszt rárom egész kódol: $-10000\le X, Y, L \le 10000$. $X$ és $Y$ a falszakasz végpontja, $L$ pedig a hossza. Pozitív $L$ jelenti a kelet-nyugat irányú, negatív pedig az észak-dél irányú falakat, utóbbi esetben értelemszerűen az abszolútérték a hossz. A bemenet végét egy 0 jelzi.

Kimenet

Az indiana.ki minden sora a egy-egy eset megoldását adja meg valós számként, két tízedes pontossággal.

Példa

indiana.beindiana.ki
14 1 1 5 6 8 2 7 2 -2 5 3 3 2 5 2 2 3 2 2 3 -2 4 3 -2 0 7 1 1 8 2 3 6 -2 4 7 2 6 6 1 6 6 -2 3 -10 0 20 -5 1 10 50 50 100 0 1.41 1.00

Tesztadatok