Túlélő verseny
Feladat
A túlélőverseny résztvevőinek az a feladata, hogy minél több pontot gyűjtsenek csapatuk számára. Az induláskor kapnak egy térképet, melyen be van jelölve kezdeti pozíciójuk, az állomások helyei, valamint az, hogy az egyes állomások látogatása hány pontot ér. Az a cél, hogy minél több állomást látogassanak meg úgy, hogy az állomásokért kapott pontok összege maximális legyen.
A térkép egy négyzetrácsos hálón van megadva, és az állomások koordinátái pozitív egész számok. A kiindulási pont koordinátái (0,0). A csapat egy (X1,Y1) koordinátájú állomástól minden olyan (X2,Y2) koordinátájú állomáshoz mehet, amelyre
X1$\le$X2 és Y1$\le$Y2, és legalább az egyik koordináta
változik a lépéskor.
Feladat
Írj programot, amely kiszámít egy olyan útvonalat, amelyen haladva a lehető legtöbb pont gyűjthető össze!
Bemenet
A TULELO.BE állomány első sorában az állomások N (1$\le$N$\le$1000) száma van. A következő N sor mindegyike az X Y P, (0$\le$X, Y$\le$10000, 1$\le$P$\le$ 2000) egész számokat tartalmazza (egy-egy szóközzel elválasztva); ahol (X,Y) egy állomás koordinátái, P pedig az állomás meglátogatásáért járó pont. Az állomásokat a bementi állománybeli sorszámukkal azonosítjuk, azaz az i-edik állomás az állomány i+1-edik sorában van megadva.
Kimenet
A TULELO.KI állomány első sorába az elérhető maximális pontszámot kell írni. A második sorban egy olyan útvonalat kell megadni, amelyen haladva elérhető a maximális pontszám. Az útvonal az állomások sorszámait tartalmazza abban a sorrendben, ahogy azokat a csapat meglátogatja.
Példa
| TULELO.BE | TULELO.KI |
| 5 3 1 10 1 2 5 2 4 12 4 5 3 5 3 9 | 20 2 3 4 |