DAPC23-099.Exceeding Limits

The input consists of:

• One line with three integers $n$, $m$, and $t$ ($2 \leq n \leq 10^4$, $1 \leq m \leq 10^5$, $1 \leq t \leq 10^5$), the number of intersections, the number of roads, and the time within which Tim needs to reach his destination.

• $m$ lines, each with four integers $a$, $b$, $\ell$, and $v$ ($1 \leq a, b \leq n$, $a \neq b$, $1 \leq \ell, v \leq 10^5$). Each line indicates a bidirectional road between intersections $a$ and $b$ with length $\ell$ in km and speed limit $v$ in km/h.

The intersections are numbered between $1$ and $n$, inclusive.

Tim will start at intersection $1$ and drive to intersection $n$, which is guaranteed to be reachable.

Output how much Tim needs to exceed the speed limit, in km/h. If Tim can reach his destination without speeding, output $0$.

Your answer should have an absolute or relative error of at most $10^{-6}$.

Source: Delft Algorithm Programming Contest 2023 · Author: Maarten Sijm · License: CC BY-SA 4.0 · Original: https://dapc.wisv.ch · Statement adapted for AlgoLens and shared under the same license. · 40 of the 142 original test cases (the largest) are omitted here to keep the problem lightweight.