Šeštadieninė informatikos olimpiadininkų mokykla

Vieną žiemą Fantazijos karalystėje gausiai pasnigo ir visi keliai tapo nepravažiuojami. Valdžia nusprendė, kad reikia nuvalyti kelius taip, kad iš kiekvieno miesto būtų galima nuvažiuoti į bet kurį kitą, tačiau nebūtinai tiesiogiai. Kad šis darbas būtų padarytas kuo greičiau ir pigiau, nutarta kelius valyti taip, kad nuvalytų kelių bendras ilgis būtų mažiausias.

Žemiau pateiktas Fantazijos karalystės žemėlapio pavyzdys. Miestai žymimi apskritimu apvestais numeriais. Kelio ilgį nurodo skaičius, parašytas ties atitinkama atkarpa.

image

1 pav.: Fantazijos karalystės žemėlapis Keliai, kuriuos reikia nuvalyti, pažymėti storomis linijomis. Nuvalytų kelių ilgis mažiausias.

Visuose keliuose eismas dvipusis. Kiekvienas jungia du skirtingus miestus. Fantazijos karalystės kelių tinklas yra toks, kad iš bet kurio miesto (savaime suprantama, kai keliai nebuvo užsnigti), galima nuvažiuoti į bet kurį kitą – tiesiogiai ar per tarpinius miestus.

Užduotis

Parašykite algoritmą, kuris rastų tokį kelių rinkinį, kad juos nuvalius iš bet kurio miesto būtų galima patekti į bet kurį kitą, o bendras nuvalytų kelių ilgis būtų mažiausias. Jei galimi keli sprendimo variantai, pakanka pateikti bet kurį vieną.

Pradiniai duomenys

Pirmoje eilutėje įrašytas miestų skaičius . Miestai sunumeruoti nuo 1 iki .

Toliau byloje pateikiama eilučių, kuriose įrašyta po tarpais atskirtų teigiamų sveikųjų skaičių: –toje eilutėje surašyti kelių ilgiai nuo –ojo miesto iki visų kitų miestų, čia –asis –osios eilutės skaičius reiškia kelio, jungiančio miestus ir , ilgį. Jei tarp miestų ir nėra tiesioginio kelio, tai kelio ilgis žymimas nuliu.

Nė vienas pradinis duomuo neviršija maxint. Bendras visų kelių ilgis neviršija maxlongint.

Atkreipkite dėmesį, kad –asis skaičius –oje eilutėje visada sutaps su –uoju skaičiumi –oje eilutėje, nes kiekvienu keliu galima važiuoti į abi puses. Be to, –asis skaičius –oje eilutėje visada yra 0, nes nėra kelių – kilpų.

Rezultatai

Pirmoje eilutėje įrašykite bendrą valomų kelių ilgį.

Likusiose eilutėse nurodykite valomus kelius – po vieną į eilutę. Kelias aprašomas dviem skaičiais – miestų, kuriuos jungia šis kelias, numeriais.

Valomų kelių pateikimo tvarka nesvarbi. Nurodant konkretų kelią, jį nusakančių miestų numeriai gali būti pateikiami bet kokia tvarka.

Pavyzdžiai

6
 0 20 0  0  0
20  0 7 15  0
 0  7 0  8  7
 0 15 8  0 10
 0  0 7 10  0

42
2 1
3 2
5 3
4 3

Pavyzdys atitinka sąlygoje pateiktą žemėlapį. Šiuo atveju uždavinys turi tik vieną sprendinį, tačiau jis gali būti pateiktas nebūtinai taip, kaip parodyta pavyzdyje. Pirmoji eilutė turi būti ta pati, o bet kurios kitos eilutės gali būti sukeistos  vietomis ir jose esantys skaičiai taip pat gali būti sukeisti tarpusavyje.

Ribojimai