Programozás‎ > ‎Feladatok‎ > ‎Gyalogtúra‎ > ‎

Megoldás

Algoritmus

Első lépésben beolvassuk az adatokat, és felépítjük belőle Magyarország "térképét". Ehhez egy gráfot állítunk elő, melynek csúcsai a települések, és két csúcs között akkor megy él, ha távolságuk legfeljebb 20 km. A távolság a földrajzi koordinátákból például a Vincenty-formulával határozható meg (http://en.wikipedia.org/wiki/Great-circle_distance).

Ezután az összes START-CÉL pár esetén szélességi bejárást indítunk a kiinduló településnek megfelelő csúcsból. A bejárás során beállítjuk az "apa-pointereket" is, hogy ki tudjunk írni egy legrövidebb utat.

Kódok

Mezei Balázs (C++): mb_tura.cpp
Erben Péter (java): gyalogtura.java