Žiema fantazijos karalystėje

Pradinių duomenų failas:

ziema.in  

Rezultatų failas:

ziema.out  

Laiko apribojimas:

1 s.  

Atminties apribojimas:

16 Mb.  

Užduotis

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.

Pateiktame paveiksle – Fantazijos karalystės žemėlapio pavyzdys. Miestai žymimi apskritimu apvestais numeriais. Kelio ilgį nurodo skaičius, parašytas ties atitinkama atkarpa. 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.

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 pradinių duomenų failo eilutėje įrašytas miestų skaičius n (2 <= n <= 170). Miestai sunumeruoti nuo 1 iki n.

Toliau faile pateikiama n eilučių, kuriose įrašyta po n tarpais atskirtų teigiamų sveikųjų skaičių: i-toje eilutėje surašyti kelių ilgiai nuo i-ojo miesto iki visų kitų miestų, čia j-asis i-osios eilutės skaičius reiškia kelio, jungiančio miestus i ir j, ilgį. Jei tarp miestų i ir j 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 j-asis skaičius i-oje eilutėje visada sutaps su i-uoju skaičiumi j-oje eilutėje, nes kiekvienu keliu galima važiuoti į abi puses. Be to, i-asis skaičius i-oje eilutėje visada yra 0, nes nėra kelių – kilpų.

Rezultatai

Pirmoje rezultatų failo 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

 5 
 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