Fișierul intrare/ieșire | cotoroanta.in, cotoroanta.out | Sursă | ad-hoc |
---|---|---|---|
Autor | clasică | Adăugată de | 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 |
Vezi soluțiile trimise | Statistici
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.