Problem S
Vairuotojai
Languages
de
en
et
is
lt
sv
Užduotis
Tarptautinė pervežimų kompanija vadinasi "Vienišiai", nes visi vairuotojai dirba po vieną. Vadovams labai svarbu klientams greitai ir tiksliai atsakyti, ar vairuotojai galės pervežti jų prekes iš miesto $a$ į miestą $b$.
Vairuotojų darbas reikalauja atsakomybės ir budrumo, dėl to jie privalo pailsėti viešbutyje ne rečiau nei kas $p$ valandų. Kiekviename mieste yra viešbučių. Naudodamiesi informacija apie miestus ir juos jungiančius kelius, parašykite programą, kuri atsakytų į vadovų užklausas.
Pradiniai duomenys
Pirmojoje eilutėje yra trys sveikieji skaičiai: $N$ - miestų skaičius, $M$ - kelių skaičius, $U$ - vadovų užklausų skaičius. Miestai yra sunumeruoti nuo $1$ iki $N$.
Kitose $M$ eilučių yra pateikta informacija apie kelius. Kiekvienoje eilutėje yra trys sveikieji skaičiai: $x$, $y$ ir $t$. Šie skaičiai reiškia, kad užtrunka $t$ valandų nuvažiuoti iš miesto $x$ į miestą $y$. Visi keliai yra dvipusiai ir keliauti abiem kryptimis užtrunka tiek pat laiko, todėl visada $x < y$. Tarp dviejų miestų yra tik vienas tiesioginis kelias.
Kitose $U$ eilučių yra pateiktos vadovų užklausos. Kiekvieną užklausą aprašo trys sveikieji skaičiai: $a$ - pradinio miesto numeris, $b$ - galutinio miesto numeris, $p$ - ilgiausias laikas, kiek vairuotojas gali važiuoti be poilsio. Visada galioją sąlyga: $a < b$.
Rezultatai
Programa atsakymus į užklausas turi išvesti skirtingose eilutėse. Jūsų programa turi išvesti $\texttt{TAIP}$, jei vairuotojas gali saugiai pervežti krovinį tarp miestų $a$ ir $b$. Jei to padaryti negalima, programa turi išvesti $\texttt{NE}$.
Ribojimai
-
$1 \leq N, M, U \leq 200\, 000$
-
$1 \leq x, y, a, b \leq N$
-
$1 \leq t, p \leq 10^9$
Dalinės užduotys
|
Nr. |
Taškai |
Papildomi ribojimai |
|
1 |
10 |
$1 \leq N, M \leq 10\, 000$ ir $t$ yra toks pats visiems keliams. |
|
2 |
11 |
$1 \leq N, M \leq 10\, 000$ ir $U \le 10\, 000$. |
|
3 |
11 |
$1 \leq N, M \leq 10\, 000$ ir $t \le 50$. |
|
4 |
23 |
$1 \leq N, M \leq 10\, 000$. |
|
5 |
45 |
Papildomų ribojimų nėra. |
Pavyzdžiai
Nors kelias tarp miestų 1–5 egzistuoja ($1 \rightarrow 3 \rightarrow 5$), tarp miestų 1–3 reikia važiuoti 9 valandas, t.y., ilgiau nei daugiausiai leidžiama (6 valandas).
Kelio tarp miestų 3–4 nėra.
Yra tiesioginis kelias tarp miestų 2–4. Tarp šių miestų galima nuvažiuoti nepažeidžiant maksimalaus darbo valandų kiekio.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 3 3 1 3 9 2 4 2 3 5 8 1 5 6 3 4 100 2 4 3 |
NE NE TAIP |
