Fișierul intrare/ieșire zapada.in, zapada.out Sursă Pregătire clasele 11-12
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu 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
open book Poți vedea testele pentru această problemă accesând atașamentele .

Zapada (clasele 11 și 12)

Narnia este formată din N castele numerotate de la 1 la N, legate între ele prin M străzi cu dublu sens. În Narnia, iarna nu-i ca vara și de aceea ninge. Primarul știe cât costă deszăpezirea fiecărei străzi pe timp de un an. El dorește să afle costul minim C0 pentru a deszăpezi un set de străzi care să permită circulația între oricare două castele. Ulterior, Primăria Narnia construiește câte o stradă nouă pe an, timp de K ani. Primarul dorește să recalculeze costul minim Ci al întreținerii rețelei de străzi în fiecare an (i = 1, 2, ..., K).

Date de intrare

Fișierul de intrare zapada.in conține

  • pe prima linie numerele N, M și K, separate prin spații;
  • pe următoarele M linii tripleți x y c cu semnificația „între castelele x și y există un drum care poate fi deszăpezit cu costul c”;
  • pe ultimele K linii tripleți xi yi ci cu semnificația „în al i_-lea an se construiește un drum între castelele _xi și yi care poate fi deszăpezit cu costul ci”.

Date de ieșire

În fișierul de ieșire zapada.out se vor tipări K + 1 linii conținând, în ordine, valorile C0, C1, ..., CK.

Restricții

  • 1 ≤ N ≤ 10.000
  • 1 ≤ M ≤ 100.000
  • 1 ≤ K ≤ 1.000
  • 1 ≤ c, ci ≤ 100.000
  • Între oricare două castele există (sau se construiește) cel mult un drum.
  • Se garantează că între oricare două castele există cel puțin un drum, direct sau indirect.

Exemplu

zapada.in zapada.out explicații
6 9 3
1 2 3
1 3 1
1 4 8
1 6 3
2 3 4
3 4 3
4 5 4
4 6 6
5 6 2
1 5 2
2 5 4
2 4 1
12
11
11
9
Costul minim se obține, de exemplu, cu străzile (1, 2), (1, 3), (1, 6), (3, 4), (5, 6).
Costul minim se obține, de exemplu, cu străzile (1, 2), (1, 3), (1, 5), (3, 4), (5, 6).
Idem.
Costul minim se obține, de exemplu, cu străzile (1, 3), (1, 5), (2, 4), (3, 4), (5, 6).

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii