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.be | indiana.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
