CSES - Datatähti 2022 alku - Tietoverkko
  • Language:
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Tietoverkossa on nn tietokonetta ja n1n-1 kahden koneen välistä yhteyttä. Jokaisen koneparin välillä pystyy välittämään tietoa yhteyksien avulla.

Jokaisella yhteydellä on tietty siirtonopeus, ja koneiden aa ja bb välinen siirtonopeus d(a,b)d(a,b) on pienin siirtonopeus aa:n ja bb:n välisellä reitillä. Tehtäväsi on laskea summa siirtonopeuksista kaikkien koneparien välillä.

Tarkastellaan esimerkkinä seuraavaa tietoverkkoa:

Tässä tapauksessa d(1,2)=5d(1,2)=5, d(1,3)=1d(1,3)=1, d(1,4)=2d(1,4)=2, d(2,3)=1d(2,3)=1, d(2,4)=2d(2,4)=2 ja d(3,4)=1d(3,4)=1, joten nopeuksien summa on 1212.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku nn: tietokoneiden määrä. Tietokoneet on numeroitu 1,2,,n1,2,\dots,n.

Tämän jälkeen on n1n-1 riviä, jotka kuvaavat yhteydet. Jokaisella rivillä on kolme lukua aa, bb ja xx: koneiden aa ja bb välissä on yhteys, jonka siirtonopeus on xx.

Tuloste

Tulosta yksi kokonaisluku: tehtävän vastaus.

Esimerkki

Syöte:

4
1 2 5
2 3 1
2 4 2

Tuloste:

12

Osatehtävä 1 (10 pistettä)

  • 1n1001 \le n \le 100
  • 1x1001 \le x \le 100

Osatehtävä 2 (15 pistettä)

  • 1n50001 \le n \le 5000
  • 1x1091 \le x \le 10^9

Osatehtävä 3 (75 pistettä)

  • 1n21051 \le n \le 2 \cdot 10^5
  • 1x1091 \le x \le 10^9