| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
A worldwide logistics company is called Loners since all of the drivers ride alone. It is very important to the managers of the company to be able to answer their clients quickly and accurately about whether or not the drivers are going to deliver their goods safely from city a to city b.
The driver’s job demands responsibility and alertness. For this reason, they are required to rest at a hotel no less frequently than every p amount of hours. The are hotels located at every city. Using the information you have about cities and roads that connect them, write a program that would answer to the queries of the managers.
On the first line three integers separated by spaces are presented: N – number of cities, M – number of roads, U – number of manager queries. The cities are numbered from 1 to N.
On the following M lines, there is information about the roads presented. On each of the lines there are three integers separated by spaces: x, y and t. These integers describe that it takes t time to drive from city x to city y. The roads are always two-way and it always takes the same amount of time to ride both ways. Therefore, the the condition x < y is always valid in this data. The two cities can only have one direct way between them.
On the remaining U amount of lines, the queries of the managers are presented. On each of the U lines, three integers are presented: a – the number of the initial city, b – the number of the end city, p – maximum amount of time that the driver can drive without rest. The condition a < b will be valid.
For each query, your program has to output TAIP (Lithuanian for yes) on a separate line in case the driver can safely deliver the goods between cities a ir b. If he cannot do that, the program has to output NE (Lithuanian for no).
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | 1 ≤ N, M ≤ 10 000, t is same for all roads |
| 2 | 11 | 1 ≤ N, M ≤ 10 000, U ≤ 10 000 |
| 3 | 11 | 1 ≤ N, M ≤ 10 000, t ≤ 50 |
| 4 | 23 | 1 ≤ N, M ≤ 10 000 |
| 5 | 45 | 1 ≤ N, M ≤ 200 000 |
5 3 3 1 3 9 2 4 2 3 5 8 1 5 6 3 4 100 2 4 3
NE NE TAIP
Even though the road between cities 1—5 exists (1 → 3 → 5), it is needed to drive for 9 hours between cities 1—3, i.e. more than the maximum amount of 6 hours.
The road between 3—4 does not exist.
There is a direct way between cities 2—4. It is possible to travel between these cities in the time that is allowed.
Olympiad > Lithuanian Olympiad in Informatics > Lithuanian Olympiad in Informatics 2016/2017 > National Round (2) > 10-12 Classes ?번