| Fişierul intrare/ieşire: | rutier.in, rutier.out | Sursă | All You Can Code 2008 |
| Autor | Mihai Ciucu | Adăugată de |  Gogu Marian •gogu |
| Timp execuţie pe test | 0.775 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |  5/5 |
Vezi solutiile trimise | Statistici
Transport Rutier
Ministrul Transportului, Braian Tasescu, a ajuns la concluzia ca are nevoie de o crestere a popularitatii sale pentru a aspira la functia de presedinte al tarii. De aceea, el vrea sa puna la punct un program prin care incearca intretinerea cat mai buna a unui sistem de transport rutier vital tarii.
Deocamdata el este interesat de cele mai importante N orase ale tarii si vrea ca sistemul de transport sa fie format din N-1 strazi astfel incat fiecare oras sa fie legat de capitala (orasul cu indicele 1) si costul total de intretinere a strazilor sa fie cat mai mic. Desi el a gasit initial sistemul optim de transport, pe viitor se mai construiesc M strazi noi intre cele N orase asa ca de multe ori e mai bine sa modifici sistemul astfel incat costul intretinerii lui sa fie minim.
Date de intrare
Prima linie a fisierului de intrare contine numarul intreg N iar pe fiecare din urmatoarele N-1 linii se vor afla informatii despre sistemul initial, pe linia i aflandu-se doua numere intregi K si C, reprezentand orasul cel mai apropiat de capitala de care este legat orasul i si respectiv costul anual de intretine a strazii care leaga cele doua orase. Daca un oras e legat direct de capitala atunci K=1.
Linia N+1 contine numarul M iar urmatoarele M linii contin 3 numere intregi X, Y, C, care reprezinta faptul ca tocmai a fost construit un drum intre orasele X si Y care are costul anual de intretinere C.
Date de iesire
In fisierul de iesire se vor scrie M linii, linia i continand un numar intreg reprezentant costul intretinerii sistemului dupa ce au mai fost construite i strazi.
Restrictii
- 1 ≤ N ≤ 50.000
- 1 ≤ M ≤ 150.000
- costul anual de intretinere al oricarei strazi este un numar natural cel mult egal cu 1.000.000
Exemplu
| rutier.in | rutier.out |
|---|---|
| 9 1 4 2 6 1 10 3 6 3 7 5 2 2 3 2 6 6 8 4 3 3 1 3 8 1 3 3 7 6 6 7 4 5 2 2 | 37 34 33 33 30 26 |
