Problem B
Vairuotojai
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 |
