P15803 [GESP202603 Level 7] Logistics Network

Related multiple-choice and true/false questions: .

A logistics network consists of $n$ cities and $m$ bidirectional roads. Each road has two attributes: - Transport cost $w_i$. - Scenic rating $b_i$. When a truck transports goods from city $1$ to city $n$, it needs to pay the sum of the transport costs of the roads it travels on. To promote tourist routes, the logistics company offers a discount policy: along the transport path, the transport cost of the road with the **highest scenic rating** can be waived. If there are multiple roads whose scenic rating ties for the maximum, only the cost of **one** of them is waived. Please compute the minimum transport cost from city $1$ to city $n$.

The first line contains two integers $n, m$, representing the number of cities and the number of roads. The next $m$ lines each contain four integers $u, v, w, b$, indicating a bidirectional road connecting city $u$ and city $v$, where $w$ is the transport cost and $b$ is the scenic rating.

Output one integer, representing the minimum cost from city $1$ to city $n$. If city $n$ cannot be reached, output `-1`.

### Sample Explanation Path $1\to 2\to 3$: cost $10+20$, maximum scenic rating $6$ (edge $2-3$). Waive $20$, total cost $10$. Path $1\to 3$: cost $100$, maximum scenic rating $1$ (edge $1-3$). Waive $100$, total cost $0$. ### Constraints $1\leq n\leq 5000$, $1\leq m\leq 5000$, $1\leq w,b\leq 10^9$. Translated by ChatGPT 5