Bergengóciában a technika fejlődésével az emberek szeretnék neten megosztani egymással a érdekes matematikai rejtvényeket, s létrehoznának egy olyan számítógépes hálózatot, amelyben mindenki el tudja juttatni a feladatát az összes többi városban élő embernek.

Bármely két várost összeköthetünk egy bizonyos költség árán. A feladatunk megtalálni azt a minimális költségű hálózatot, amelyben minden város összeköttetésben áll a többivel.

 

Írjunk programot, ami meghatározza a minimális összköltségű hálózat árát.

A bemeneti fájl első sorában a városok száma N (5<=N<=100) szerepel. A további N(N-1)/2 sor mindegyikében három adat van (szóközzel elválasztva): két város sorszáma és a két város közötti hálózat kiépítési K (1<=K<=200) költsége. 

A kimenetre hálózat kiépítéséhez szükséges minimális összköltséget kell kiírni.

A feladat forrása: Tihanyi Balázs feladata

Algoritmusok: minimális összsúlyú feszítőfa

megoldás