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 |