Programozás‎ > ‎Feladatok‎ > ‎

Falvak

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

Feladat

Készítsünk programot, ami megadja...

A. a leghosszabb utat, amiről nem lehet letérni és zsákfaluhoz vezet;

B. azokat a településeket, ahova a legtöbb út vezet (ha több is van, akkor mindegyiket);

C. azt a települést, amitől a legközelebbi szomszédja legmesszebb van (ha több is van, akkor a legkisebb sorszámút). 

Bemenet

A falvak.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, valamint a köztük lévő út hossza.

Kimenet

A falvak.ki szöveges állomány első sorába a zsákfalvakba vezető leghosszabb út hosszát; a második sorába a legtöbb utas települések sorszámát (ha több ilyen van, akkor sorszám szerint növekvő sorrendben és szóköz válassza el őket egymástól), a harmadikba pedig a település sorszámát kell írni!

Példa

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



Tesztadatok

Címkék

A feladat forrása: NTOITV 2011. 2. forduló, 11-13. évfolyam
Algoritmusok: ???

megoldás