h2. 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 perechi de numere $x y$ cu semnificația că există un coridor între camerele $x$ și [$y$]. Pe următoarele $K$ linii sunt indicate lungimile noilor coridoare. Linia corespunzătoarele anului $i$ va conține $N + i - 1$ numere.
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.
h2. Date de ieșire
În fișierul de ieșire $cotoroanta.out$ se vor scrie, în ordine, lungimea minimă de cablu pentru castelul inițial și pentru următorii $K$ ani.
Î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.
h2. Restricții
* $1 ≤ N ≤ 10.000$;
* $1 ≤ N ≤ 5.000$;
* $1 ≤ M ≤ 100.000$;
* $1 ≤ K ≤ 1.000$;
* lungimile coridoarelor sunt numere între 1 și 100.000.
* $1 ≤ K ≤ 100$;
* lungimile coridoarelor sunt numere întregi între 1 și 1.000.000.
h2. Exemplu
table(example).
|_. cotoroanta.in |_. cotoroanta.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 3 2
3 2 10
3 1 8
1 2 6
5 4 12
1 2 10 2
| 14
17
13
|
h3. 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.
== include(page="template/taskfooter" task_id="cotoroanta") ==
