Fișierul intrare/ieșire cotoroanta.in, cotoroanta.out Sursă ad-hoc
Autor clasică Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 0.5 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Cotoroanța

Castelul Cotoroanței are N camere legate prin M coridoare. Un coridor leagă exact două camere și oricare două camere sunt legate prin cel mult un coridor. Se cunoaște lungimea fiecărui coridor (camerele au dimensiuni neglijabile). În fiecare din următorii K ani, Cotoroanța își extinde castelul cu câte o cameră. Noua cameră este legată prin coridoare de toate camerele existente.

De fiecare Halloween, Cotoroanța iluminează toate camerele castelului cu instalația electrică. Ea poate construi o instalație ramificată, dar are o singură baterie și dorește să cumpere cât mai puțin cablu electric. Să se calculeze, pentru castelul inițial și pentru următorii K ani, lungimea minimă de cablu necesară.

Date de intrare

Fișierul de intrare cotoroanta.in conține, pe prima linie, valorile N, M și K. Pe următoarele M linii apar triplete de numere x y z cu semnificația că există un coridor între camerele x și y de lungime z. Pe următoarele K linii sunt indicate lungimile noilor coridoare. Linia corespunzătoarele anului i va conține N + i – 1 numere.

Date de ieșire

În fișierul de ieșire cotoroanta.out se vor scrie, în ordine cronologică, lungimile de cablu necesare pentru castelul inițial și pentru următorii K ani.

Restricții

  • 1 ≤ N ≤ 5.000;
  • 1 ≤ M ≤ 100.000;
  • 1 ≤ K ≤ 100;
  • lungimile coridoarelor sunt numere întregi între 1 și 1.000.000.

Exemplu

cotoroanta.in cotoroanta.out
3 3 2
3 2 10
3 1 8
1 2 6
5 4 12
1 2 10 2
14
17
13

Explicație

La început, instalația cea mai scurtă trece prin coridoarele (1,2) și (1,3) cu costul 6 + 8 = 14.
După un an, instalația cea mai scurtă trece prin coridoarele (2,4), (1,4) și (1,3) cu costul 4 + 5 + 8 = 17.
După doi ani, instalația cea mai scurtă trece prin coridoarele (1, 3), (1,5), (2,5) și (4,5) cu costul 8 + 1 + 2 + 2 = 13.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii