Élt az egyik Óperenciás-tengeren túli városban egy koldus, aki abból élt, hogy jártában keltében kéregetett az arra járó emberektől. A jószívű emberek adtak neki pénzt, a gonoszak pedig megsarcolták. A koldus otthon feljegyezte a térképén, hogy az egyes utcákon átlagosan mennyi pénzt szokott kapni ill. mennyi sarcot fizet, így mindig a legjövedelmezőbb útvonalon tud eljutni a céljához.
Feladat:
Készíts programot, amely megadja a koldusnak a város két pontja közötti legjövedelmezőbb útvonalat.
Bemenet:
A bemenet első részében a város leírása következik. Az útkereszteződéseket 1000-nél kisebb pozitív egész számokkal jelöljük. Az utcákat egy számhármassal jellemezzük. A számhármas első két tagja egy-egy "szomszédos" útkereszteződés azonosítója, a harmadik tag az utcában szerezhető jövedelem vagy fizetendő sarc (negatív szám esetén). Tehát a bemenet első sorában szereplő 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. Ezután következnek a kérdések számpárok formájában, amelyek a város egy-egy útkereszteződésének a kijelölésére szolgálnak. Az input végét egy -1-es szám jelzi.
Kimenet:
A kimenet tartalmazza a kérdésekben szereplő útkereszteződések (számpárok) közti legjövedelmezőbb út hosszát és az utat is. Minden válasz az út hosszával kezdődik, majd az út leírása következik az útkereszteződések vesszővel elválasztott felsorolásával.
(Nagy Tibor)