Fişierul intrare/ieşire:rutier.in, rutier.outSursăAll You Can Code 2008
AutorMihai CiucuAdăugată degoguGogu Marian gogu
Timp execuţie pe test1.55 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.inrutier.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content