Programozás‎ > ‎Feladatok‎ > ‎

Áramszünet

A BDGPROG munkacsoport informatika versenyt szervez a 150. évforduló alkalmából. A zökkenőmentes lebonyolítás érdekében az esetleges áramszünetre is fel kell készülni, ezért biztonsági tartalékként beüzemelnek egy helyi erőművet (a neve "Jövő"), és erre is rákötik a versenyben résztvevő iskolákat.

Feltételezhetjük, hogy a "Jövő"-vel összekötött iskolák számítógépei már megbízhatóan fognak működni, ezt a működést kell minimális költséggel garantálni. Nem kell mindenkit rákötni az erőműre, elég egy olyan iskolával összekötni, ami már (közvetve vagy közvetlen) rá van kapcsolódva a tartalék erőműre.

Tudjuk, hogy mely iskolák között lehetséges az összeköttetés kiépítése, és ezekben az esetekben ismerjük a kiépítés költségét. 

Feladat

Írjunk programot, ami megadja a legolcsóbb és a második legolcsóbb összekötési hálózat árát!

Bemenet

A bemenet több tesztesetet tartalmaz. Az első sor a tesztesetek számát tartalmazza. Minden teszteset első sora az iskolák N számát és a lehetséges összekötések M számát adja meg. (2 < N < 101) Ezután M sor következik három - három számmal: az összekötött iskolák sorszámával és az összekötés költségével. Az összekötések C költsége 1 és 300 közé esik. 

Kimenet

Minden kérdéshez írjuk ki a legolcsóbb és a második legolcsóbb hálózat árát! Előfordulhat, hogy két különböző legolcsóbb hálózat van, ilyenkor két egyenlő számot kell kiadni.

Példa

Bemenet  Kimenet
2
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
9 14
1 2 4
1 8 8
2 8 11
3 2 8
8 9 7
8 7 1
7 9 6
9 3 2
3 4 7
3 6 4
7 6 2
4 6 14
4 5 9
5 6 10
110 121 37 37


Tesztadatok

Készül...

Címkék

A feladat forrása: ???
Algoritmusok: minimális összsúlyú feszítőfa

megoldás