Fişierul intrare/ieşire:flota.in, flota.outSursăad-hoc
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test1.5 secLimită de memorie10240 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Flota

Mândria complexului de agrement de la Şmenu sunt plimbările cu vaporul pe salba de N lacuri legate prin M canale. Un vapor de lăţime L poate naviga între două lacuri dacă există o cale între cele două lacuri formată numai din canale de lăţime cel puţin egală cu L. Proprietarul complexului, Trăiam Binescu, doreşte să cumpere o flotă de vapoare, toate identice, care să deservească toate lacurile. Deoarece preţurile variază pentru vapoare de diverse lăţimi, Binescu îşi notează K lăţimi şi doreşte să afle, în fiecare caz, numărul minim de vapoare necesare.

Date de intrare

Fişierul de intrare flota.in conţine, pe prima linie, numerele N, M şi K.

Următoarele M linii conţin triplete de numere x y w, semnificând că între lacurile x şi y există un canal de lăţime w.

Ultimele K linii conţin câte un număr L i, semnificând o posibilă lăţime a vapoarelor de cumpărat.

Date de ieşire

În fişierul de ieşire flota.out se vor scrie K linii. Linia i va conţine un singur număr, respectiv numărul de vapoare care sunt necesare pentru lăţimea L i. Răspunsurile trebuie afişate în aceeaşi ordine cu întrebările.

Restricţii

  • 1 ≤ N ≤ 50.000
  • 1 ≤ M ≤ 1.000.000
  • 1 ≤ K ≤ 100.000
  • Între oricare două lacuri există cel mult un canal. Toate canalele au dublu sens.
  • Lăţimile canalelor şi ale vapoarelor sunt întregi, pozitive, cel mult egale cu 50.000.

Exemplu

flota.inflota.outExplicaţie
6 9 5
1 2 5
1 6 10
2 3 40
2 6 20
3 4 5
3 5 35
3 6 80
4 5 15
5 6 60
20
90
3
60
30
3
6
1
4
3
Este nevoie de 3 vapoare de lăţime 20: unul pentru grupul de lacuri (2, 3, 5, 6) şi câte unul pentru lacurile 1 şi 4.
Vapoarele de lăţime 90 nu pot naviga pe niciun canal, deci este nevoie de câte un vapor pentru fiecare lac.
Vapoarele de lăţime 3 pot naviga pe toate canalele, deci este suficient unul singur.
Este nevoie de 4 vapoare de lăţime 60: unul pentru grupul de lacuri (3, 5, 6) şi câte unul pentru lacurile 1, 2 şi 4.
Este nevoie de 3 vapoare de lăţime 20: unul pentru grupul de lacuri (2, 3, 5, 6) şi câte unul pentru lacurile 1 şi 4.
Trebuie sa te autentifici pentru a trimite solutii. Click aici