| Fişierul intrare/ieşire: | canale.in, canale.out | Sursă | ad-hoc |
| Autor | Catalin Francu | Adăugată de |  Catalin Francu •Catalin.Francu |
| Timp execuţie pe test | 0.3 sec | Limită de memorie | 2048 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Canale
Se dă o reţea de N lacuri unite prin M canale maritime bidirecţionale. Un canal uneşte fix două lacuri. Reţeaua este conexă, adică între oricare două lacuri se poate ajunge navigând pe canale. Fiecare canal are o lăţime cunoscută. Un vapor poate naviga pe un canal dacă are lăţimea cel mult egală cu lăţimea canalului.
Se dau Q interogări de tipul (u, v). Să se calculeze lăţimea maximă a unui vapor care să poată naviga între lacurile u şi v, pe orice rută.
Date de intrare
Fişierul de intrare canale.in conţine, pe prima linie, numerele N M Q în această ordine. Pe următoarele M linii se găsesc câte trei numere, u v w, cu semnificaţia că există un canal între lacurile u şi v de lăţime w. Pe următoarele Q linii se găseşte câte o pereche de numere u v reprezentând o interogare.
Date de ieşire
În fişierul de ieşire canale.out se vor tipări răspunsurile la interogări, câte un număr pe linie, în aceeaşi ordine ca la intrare.
Restricţii
- 1 ≤ N ≤ 3.000
- 1 ≤ M ≤ 50.000
- 1 ≤ Q ≤ 100.000
- lăţimile canalelor sunt numere naturale între 1 şi 60.000
Exemplu
| canale.in | canale.out | Imagine |
|---|---|---|
| 6 8 3 5 4 18 1 2 20 3 2 14 3 6 25 6 5 14 4 6 9 1 3 16 1 4 10 1 2 6 1 3 4 | 20 16 14 | 
|
Explicaţie
- Între lacurile 1 şi 2 poate naviga, pe canalul direct, un vapor de lăţime 20.
- Între lacurile 6 şi 1 poate naviga, pe ruta 6 - 3 - 1, un vapor de lăţime 16.
- Între lacurile 3 şi 4 poate naviga, pe ruta 3 - 6 - 5 - 4, un vapor de lăţime 14.
