NézetNyomtat

Falvak
Címkék > Feladat
Versenyek > Nemes Tihamér OKSzTV > 2011 > Második forduló > 11-13. évfolyam

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\le N\le 1000$) és az utak száma van ($1\le M\le 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

falvak.befalvak.ki
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