Fişierul intrare/ieşire:cotoroanta.in, cotoroanta.outSursăad-hoc
AutorclasicaAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.5 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

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