| Fişierul intrare/ieşire: | tollroads.in, tollroads.out | Sursă | ad-hoc |
| Autor | Adăugată de |  Cosmin-Mihai Tutunaru •stocarul | |
| Timp execuţie pe test | 1.25 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
TollRoads
N oraşe sunt conectate între ele prin M autostrăzi bidirecţionale, fiecare autostradă (a, b) având un cost de tranzit c ataşat. Se doreşte revizuirea sistemului de taxare, însă sunt câteva aspecte ce trebuie luate în calcul şi necesită investigaţie, deoarece o parte dintre cele N oraşe sunt centre comerciale sau turistice importante.
Cerinţă
Se doreşte să se afle răspunsul la o serie de Q întrebări de forma: (X, T) - câte dintre celelalte N-1 oraşe, au acces către oraşul X, cu o taxă totală de cel mult T către fiecare oraş?
Date de intrare
Fişierul de intrare tollroads.in conţine pe primul rând numerele N, M şi Q reprezentând numărul de oraşe, numărul de autostrăzi şi numărul de interogări. Pe fiecare din următoarele M rânduri sunt scrise câte trei numere a, b, c, separate prin câte un spaţiu, reprezentând două oraşe între care există o autostradă şi costul autostrăzii. Pe următoarele Q rânduri se află scrise câte două numere X şi T, separate prin spaţiu, reprezentând datele interogărilor, conform enunţului.
Date de ieşire
În fişierul de ieşire tollroads.out se vor scrie pe fiecare dintre primele Q rânduri câte un singur număr, reprezentând răspunsurile la interogări, în ordinea în care ele au fost puse.
Restricţii
- 1 ≤ N ≤ 10^5
- 1 ≤ M ≤ 10^5
- 1 ≤ a, b ≤ N
- 1 ≤ c ≤ 10^5
- 1 ≤ T ≤ 10^5
- 1 ≤ Q ≤10^2
- între orice două oraşe poate exista mai mult de o autostradă
Exemplu
| tollroads.in | tollroads.out |
|---|---|
| 7 8 5 1 2 1 2 3 2 2 4 4 3 5 1 4 5 1 5 6 2 1 6 5 6 7 1 1 6 1 5 1 4 2 3 4 4 | 6 5 3 3 5 |
Explicaţie
Oraşele 2,3,4,5,6,7 au acces către oraşul 1 cu taxă maximă 6
Oraşele 2,3,4,5,6 au acces către oraşul 1 cu taxă maximă 5
Oraşele 2,3,5 au acces către oraşul 1 cu taxă maximă 4
Oraşele 1,3,5 au acces către oraşul 2 cu taxă maximă 3
Oraşele 2,3,5,6,7 au acces către oraşul 4 cu taxă maximă 4
