Programozás‎ > ‎Feladatok‎ > ‎

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

Aindiana.be állomány több tesztesetet tartalmaz. Minden teszteset az falszakaszok N számával kezdődik. (2 <= N <= 1000
A következő 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 három egész kódol: -10000 <= X,Y,L <= 10000X é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

Aindiana.ki minden sora egy-egy eset megoldását adja meg valós számként, két tizedes pontossággal

Példa

Bemenet  Kimenet
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

Címkék

A feladat forrása: ACM
Algoritmusok: legrövidebb út módosított változata

megoldás