Fişierul intrare/ieşire:radiatie.in, radiatie.outSursăpreONI 2007, Runda 1
AutorMircea Bogdan PasoiAdăugată dedominoMircea Pasoi domino
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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

Cum se trimit solutii?

remote content