| Fişierul intrare/ieşire: | radiatie.in, radiatie.out | Sursă | preONI 2007, Runda 1 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Mircea Pasoi •domino |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate |  5/5 |
Vezi solutiile trimise | Statistici
Radiatie
Zaharel este cercatator de fizica nucleara si lucreaza la un complex de cercetare secret format din N laboratoate, numerotate convenabil cu numere de la 1 la N. De asemenea, aceste laboratoare sunt conectate prin M tunele bidirectionale, de diverse lungimi. Desi laboratoarele sunt concepute astfel incat cercetatorii sa nu fie expusi la radiatii, tunelele nu protejeaza complet, astfel incat daca un cercetator foloseste un anumit tunel de legatura va fi expus la un nivel de radiatii direct proportional cu lungimea tunelului.
Zaharel are de efectuat K drumuri intre diverse perechi de laboratoare. Stiind ca expunerea pentru un timp indelungat la radiatii are efecte daunatoare, el va alege mereu un drum in care lungimea maxima a unui tunel parcurs este minima. Determinati care vor fi drumurile pe care le va alege Zaharel.
Date de intrare
Prima linie a fisierului de intrare radiatie.in va contine numerele naturale N, M, K separate prin spatii. Urmatoarele M linii vor contine cate trei numere naturale a b c cu semnificatia ca exista un tunel intre laboratorul cu numar a si laboratorul cu numar b, de lungime c. In continuare, urmatoarele K linii vor contine perechi de numere naturale x y avand semnificatia ca Zaharel va efectua un drum intre laboratoarele x si y.
Date de iesire
Fisierul de iesire radiatie.out va contine K linii, fiecare continand lungimea maxima minima considerand tunelele parcurse de Zaharel pentru fiecare drum. Rezultatele se vor afisa in ordinea in care sunt date cele K drumuri in fisierul de intrare.
Restrictii
- 1 ≤ N, K ≤ 15.000
- 1 ≤ M ≤ 30.000
- Lungimea unui tunel este un numar natural din intervalul [1, 109]
- Un drum reprezinta o succesiune de laboratoare a1, a2 ... ax cu proprietatea ca exista un tunel intre ai si ai+1 pentru orice i < x
- Se garanteaza ca exista cel putin un drum intre fiecare din cele K perechi de laboratoare din fisierul de intrare
Exemplu
| radiatie.in | radiatie.out |
|---|---|
| 6 6 8 1 2 5 2 3 4 3 4 3 1 4 8 2 5 7 4 6 2 1 2 1 3 1 4 2 3 2 4 5 1 6 2 6 1 | 5 5 5 4 4 7 4 5 |
