Fișierul intrare/ieșire | canale.in, canale.out | Sursă | ad-hoc |
---|---|---|---|
Autor | Cătălin Frâncu | Adăugată de | Cătălin Frâncu • Catalin.Francu |
Timp de execuție pe test | 0.3 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate | N/A |
Vezi soluțiile trimise | Statistici
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.