Fişierul intrare/ieşire:zapada.in, zapada.outSursăPregătire clasele 11-12
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.5 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

Zapada

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.inzapada.outexplicaţ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 sa te autentifici pentru a trimite solutii. Click aici