NézetNyomtat

Legrövidebb hálózat
Címkék > Feladat
Címkék > Hiányzó csatolt fájl

Legrövidebb hálózat

Néhány várost üvegszálas internet kapcsolattal kötünk össze. A kábelek egyenes vonalban vezethetők két pont között. Felvehetünk csomópontokat a városokon kívül is.
Célunk a hálózat összhosszának minimalizálása.

Feladat

Írj programot, amely a városok koordinátáinak ismeretében megadja az optimális hálózat összhosszát. Amennyiben új csomópontokat vettünk fel, ki kell írni a csomópontok koordinátáit is. Meg kell továbbá adni, hogy mely pontok vannak közvetlenül kábellel összekötve a hálózatban.

Bemenet

Az SNP.BE állomány első sora a városok N számát tartalmazza. ($2 \lt N \lt 7$). További N sorban a városok koordinátái következnek X Y sorrendben, szóközzel elválasztva. ($0 \le X$, $Y \le 100$).

Kimenet

Az SNP.KI állomány első sorába a minimális összhossz értékét írjuk tízedestört alakban. A következő sorba a szükséges csomópontok C száma kerüljön. Ha ez nagyobb nullánál, akkor a következő C sor a csomópontok koordinátáit tartalmazza. Végül az összekötésben használt szakaszokat soroljuk fel, végpontjaikkal megadva.
A városok neve: v1,v2,v3,...
A csomópontok neve c1, c2, ...
Az összekötő szakaszok megadása pl: v1 - c2

Példák

SNP.BESNP.KI
3 0 0 30 0 80 0 80.0 0 v1 - v2 v2 - v3
4 0 0 0 100 100 0 100 100 273.2055362658948 2 50 29 50 71 v1 - c1 v2 - c1 v3 - c2 v4 - c2 c1 - c2

Tesztadatok

feloldhatatlan link: snp.zip (/szakkor/bdg/0708/05ora/snp/snp.zip)