Fișierul intrare/ieșire flota.in, flota.out Sursă ad-hoc
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 1.5 sec Limită de memorie 10240 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in flota.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii