P17462 [GESP202609 Level 8] Last Train

There are $n$ subway stations and $m$ subway lines in a city. The stations are numbered $1,2,\ldots,n$ in order. For the $i$-th subway line ($1\le i\le m$), trains run in one direction from station $u_i$ to station $v_i$. The latest departure time is minute $l_i$, and the travel time is $t_i$ minutes. From minute $0$ to minute $l_i$, there is a train departing from station $u_i$ every minute. A train that departs at minute $x$ ($0\le x\le l_i$) will arrive at station $v_i$ at minute $x+t_i$. Passengers on this train may transfer to any train of any line departing from station $v_i$ at minute $x+t_i$ or later. Now there are $q$ queries. The $i$-th query ($1\le i\le q$) gives the starting station $x_i$, the destination station $y_i$, and the departure time $s_i$. You need to determine whether it is possible to reach station $y_i$ when departing from station $x_i$ at minute $s_i$. Departing from station $x_i$ at minute $s_i$ means you may take any train on any line that departs from station $x_i$ at minute $s_i$ or later.

The first line contains three positive integers $n,m,q$, representing the number of stations, the number of subway lines, and the number of queries. The next $m$ lines each contain four integers $u_i,v_i,l_i,t_i$, representing the starting station, the ending station, the latest departure time, and the required travel time of the line. The next $q$ lines each contain three integers $x_i,y_i,s_i$, representing the trip start, the trip destination, and the departure time.

Output $q$ lines in total. For each query, if it is possible to reach station $y_i$ when departing from station $x_i$ at minute $s_i$, output `Yes`; otherwise output `No`. Note that the output is case-sensitive.

For $40\%$ of the test points, it is guaranteed that $q\le 100$. For all test points, it is guaranteed that: - $1\le n\le 500$ - $1\le m\le 1000$ - $1\le q\le 5\times 10^5$ - $1\le u_i,v_i,x_i,y_i\le n$ - $0\le l_i,s_i\le 10^5$ - $1\le t_i\le 10^4$ Translated by ChatGPT 5