P15441 [Lanqiao Cup 2025 National Python/Java Postgraduate Group] Shortest-Time Path.

An explorer needs to pass through a maze full of spacetime rifts. There are $n$ spacetime rifts (called nodes), numbered $1 \sim n$. The explorer may stay at any node for any length of time. There are $m$ paths between the rifts. Each path is described by $(u_i, v_i, w_i, s_i, e_i)$, meaning there is an undirected path between node $u_i$ and node $v_i$. Traversing this path takes time $w_i$, and the explorer can enter and traverse it only when the current time is within the interval $[s_i, e_i]$ (therefore, after traversing this path, the arrival time at $v_i$ must be within $[s_i + w_i, e_i + w_i]$). At the same time, the explorer has a chance to adjust the flow of time: when traversing some path, they may ignore the time restriction $[s_i, e_i]$. This skill can be used at most $k$ times. Initially, the explorer is at node $1$ at time $0$. What is the minimum time needed to reach node $n$ from node $1$?

The first line contains three integers $n, m, k$, separated by one space. The next $m$ lines each contain five integers $u_i, v_i, w_i, s_i, e_i$, separated by one space, describing the $i$-th path. The graph may contain multiple edges and self-loops.

Output one line containing one integer, the answer. If there is no possible path, output $-1$.

### Sample Explanation For Sample 1: You can directly take the path $1 \to 3$, which takes 6 units of time. Taking $1 \to 2 \to 3$ takes 8 units of time, because after reaching node 2 you need to wait until time 5 to continue. For Sample 2: Since you have one chance to use the skill, first take $1 \to 2$, then use the skill once on $2 \to 3$, for a total time of 4. ### Constraints and Conventions For $10\%$ of the testdata, $2 \le n \le 5$. For $20\%$ of the testdata, $2 \le n \le 10$. For $40\%$ of the testdata, $2 \le n \le 100$. For $60\%$ of the testdata, $2 \le n \le 1000$. For $80\%$ of the testdata, $2 \le n \le 10000$. For all testdata, $2 \le n \le 50000$, $1 \le m \le \min\left(\dfrac{n(n-1)}{2}, 10^5\right)$, $0 \le k \le 10$, $1 \le u_i, v_i \le n$, $0 \le s_i, e_i \le 4 \times 10^3$. Translated by ChatGPT 5