Fișierul intrare/ieșire canale.in, canale.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 0.3 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii