Fişierul intrare/ieşire:online.in, online.outSursăGrigore Moisil 2008, clasele 11-12
AutorClara Ionescu, Csaba PatcasAdăugată dewefgefAndrei Grigorean wefgef
Timp execuţie pe test0.05 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Online

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.

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.

Date de intrare

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.

Date de iesire

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.

Restrictii

  • 1 < N ≤ 200
  • 1 < M ≤ 10000
  • 1 < K ≤ 10000
  • 1 ≤ costul unui drum intre doua orase ≤ 250
  • Drumurile dintre orase sunt bidirectionale

Exemplu

online.inonline.out
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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content