== include(page="template/taskheader" task_id="online") ==
Poveste si cerinta...
Intr-o tara imaginara trebuie construita o retea de drumuri intre $N$ orase. Ministrul Transporturilor a apelat la $M$ firme de constructii si le-a cerut sa estimeze costul unor drumuri care la randul lor sa lege doua orase, fara sa treaca prin altele. Din cele $M$ oferte care se refereau la $M$ drumuri diferite (posibile de construit), Ministrul Transporturilor a ales un numar minim de perechi de orase intre care se va construi un drum direct, astfel incat din orice oras sa se poata calatori in orice oras direct sau prin intermediul unor drumuri care trec prin alte orase cu cost minim.
Constructia urma sa inceapa peste $K$ saptamani. In aceasta perioada Ministrul Transporturilor a primit saptamanal cate o oferta noua, referitoare la alte posibile drumuri care vor lega in mod direct alte doua orase dar si la unele ofertate deja, dar cu alte costuri. Ministrul Transporturilor trebuie sa actualizeze proiectul si sa stabileasca - saptamanal - care dintre drumuri sa le construiasca peste cele $K$ saptamani.
h2. Cerinta
Determinati proiectul initial. Apoi, pe baza ofertelor nou sosite pe parcursul celor $K$ saptamani, determinati cate un proiect nou astfel incat costul total al productiei sa fie minim.
h2. Date de intrare
Fisierul de intrare $online.in$ ...
Pe prima linie a fisierul de intrare $online.in$ se afla doua numere naturale $N$ si $M$, separate printr-un spatiu, reprezentand numarul oraselor si numarul ofertelor. Pe fiecare dintre urmatoarele $M$ linii se afla cate trei numere naturale, separate prin cate un spatiu, primele doua reprezentand numerele de ordine ale celor doua orase care s-ar lega direct prim drumul respectiv, si al treilea costul drumului respectiv. Pe urmatoarea linie se afla numarul natural $K$, reprezentand numarul de saptamani in care proiectul urmeaza sa fie imbunatatit. Pe urmatoarele $K$ linii sunt scrie cate trei numere naturale, avand semnificatia scrisa mai sus.
h2. Date de iesire
In fisierul de iesire $online.out$ ...
In fisierul de iesire $online.out$ se vor scrie costurile proiectelor: a celui initial, apoi ale celor $K$ actualizari. Prin cost intelegem suma costurilor drumurilor selectate.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 < N ≤ 200$
* $1 < M ≤ 10000$
* $1 < K ≤ 10000$
* $1 ≤ costul unui drum intre doua orase ≤ 250$
* Drumurile dintre orase sunt bidirectionale
h2. Exemplu
table(example). |_. online.in |_. online.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 7
1 2 1
2 3 7
1 5 5
3 4 3
4 5 4
1 3 2
2 4 6
2
3 5 2
1 4 3
| 10
8
8
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="online") ==
