Programozás‎ > ‎Feladatok‎ > ‎

Falu

Ismerjük egy megye települései (falvak, városok) közötti utak hosszát. Zsákfalunak nevezzük azt a falut, ahova csak egyetlen út vezet (és onnan tovább már nem lehet menni, csak visszafelé). A településeket sorszámmal azonosítjuk. 

Feladat

Készíts programot, amely megadja:

A. a zsákfalvak számát;

B. azt a települést, ahova a legtöbb út vezet szomszédos településről;

C. az egymáshoz legközelebbi 2, nem szomszédos települést (ha több ilyen van, akkor bármelyik megadható) 

Bemenet

A falu.be szöveges állomány első sorában a települések (2 <= N <= 1000) és az utak száma van (1 <= M <= 100000), egy szóközzel elválasztva. A következő M sor mindegyikében három egész szám van, egy-egy szóközzel elválasztva: egy-egy út két végpontjának sorszáma és a köztük levő út hossza. 

Kimenet

A falu.ki szöveges állomány első sorába a zsákfalvak számát; a második sorba a legtöbb utas település sorszámát (ha több van, bármelyik megadható), a harmadikba pedig a két legközelebbi település sorszámát (szóközzel elválasztva, ha több egyforma távolság is van, bármelyik településpár megadható) kell írni! 

Példa

Bemenet  Kimenet
6 7
1 2 10
2 3 15
2 4 10
2 5 5
3 5 5
4 5 15
5 6 5
 2
2
3 6


Tesztadatok

Címkék

A feladat forrása: NTOITV 2011. 2. forduló, 9-10. évfolyam
Algoritmusok: 

megoldás