P9734 [JOISC 2021] Escape Route (Day2)

Submitting this problem on Luogu is **not** interactive. Please pay attention to the submission method. The testdata for this problem is very large, and the judge may need 1–2 minutes to load. [English statement](https://www2.ioi-jp.org/camp/2021/2021-sp-tasks/day2/escape_route-en.pdf).

The IOI Kingdom uses Byou (seconds) as the unit of time, and divides one day into $S$ Byou, called times $0,1,\dotsc,S-1$. In the IOI Kingdom, there are $N$ cities and $M$ undirected roads, all numbered starting from $0$. It is guaranteed that every pair of cities is connected. The $i$-th road connects cities $A_i$ and $B_i$, and it takes exactly $L_i$ Byou to traverse. Every day, after time $C_i$, the $i$-th road starts being inspected until the end of the day. The JOI Organization is a secret group active in the IOI Kingdom. For confidentiality, its members must not be inspected on roads. If a member wants to traverse road $i$, they must arrive at one endpoint of this road no later than time $C_i-L_i$. Inspections on a road do not affect the cities at its endpoints. Now there are $Q$ members of the JOI Organization, numbered starting from $0$. On some day, member $j$ starts from city $U_j$ at time $T_j$ and wants to go to city $V_j$. A member may stay in any city for any amount of time. Note that this member may spend more than one day on the trip. For each member, compute the shortest time they need, accurate to Byou.

The first line contains four positive integers $N,M,S,Q$. The next $M$ lines describe the roads. Line $i$ contains four positive integers $A_{i-1},B_{i-1},L_{i-1},C_{i-1}$. The next $Q$ lines describe the queries. Line $i$ contains three positive integers $U_{i-1},V_{i-1},T_{i-1}$.

Output $Q$ lines. Line $i$ contains the shortest travel time required for member $i-1$.

Constraints for $100\%$ of the data: - $2 \leq N \leq 90$. - $N-1 \leq M \leq \dfrac{N(N-1)}{2}$. - $2 \leq S \leq 10^{15}$. - $1 \leq Q \leq 3 \times 10^6$. - $0 \leq A_i,B_i \leq N-1$. - $A_i \neq B_i$. - $\forall i,j \in [0,M-1]$，if $i \neq j$, then $(A_i,B_i) \neq (A_j,B_j)$ and $(A_i,B_i) \neq (B_j,A_j)$. - $1 \leq L_i \leq C_i < S$. - Starting from any city and traversing some edges, it is possible to reach any other city. - $0\leq U_j,V_j \leq N-1$. - $U_j \neq V_j$. - $0 \leq T_j < S$. For $5\%$ of the score: $N \leq 40, Q \leq 1000$. For another $20\%$ of the score: $N \leq 40, U_j=0$. For another $10\%$ of the score: $N \leq 40$. For another $35\%$ of the score: $N \leq 60$. **It is recommended to use fast I/O.** Translated by ChatGPT 5