Fişierul intrare/ieşire:canale.in, canale.outSursăad-hoc
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.3 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise

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.incanale.outImagine
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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici