== include(page="template/taskheader" task_id="tollroads") ==
Poveste şi cerinţă...
$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.
h2. 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ş?
h2. Date de intrare
Fişierul de intrare $tollroads.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $tollroads.out$ ...
Î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.
h2. 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ă
h2. Exemplu
table(example). |_. tollroads.in |_. tollroads.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. 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
== include(page="template/taskfooter" task_id="tollroads") ==
