P4453 [CTT] Flight Plan

1. wqs likes flight simulation. 2. clj started an airline named Shenben Airlines (Shénbén). Since clj also wants to play games, you are in charge of running the company. Note: This is only a thematic background and does not correspond to real/simulated flight.

Shenben Airlines has a flight from $A$ to $B$ and needs to plan the most economical route. To simplify, we assume the ground is a plane at height $0$, with $N$ waypoints and $M$ bidirectional airways. Each airway connects two waypoints and has two parameters $H$ and $W$, meaning that traversing this airway at altitude $h$ costs $(H - h)^2 + W$. At each waypoint you may climb or descend; each unit of climb costs $C$, while descending is free. Waypoint $0$ is $A$, and waypoint $N - 1$ is $B$.

The first line contains 3 positive integers $N$, $M$, and $C$, as described above. The next $M$ lines each contain 4 integers $u, v, H, W$, indicating there is an airway between $u$ and $v$ with parameters $H$ and $W$.

Output a single line with one integer, the minimum cost from $A$ to $B$.

Constraints: - For 10% of the testdata: $N, M \le 5$, $H \le 200$. - Additionally, for 20% of the testdata: $N \le 100$, $M \le 500$, $H \le 100$. - For all testdata: $N \le 2000$, $M \le 10000$, $C \le 10$, $0 \le u, v < N$, $0 \le H \le 10^5$, $0 \le W \le 2 \times 10^5$. The input guarantees the answer does not exceed a 32-bit signed integer. Translated by ChatGPT 5