A7288. [GESP202603 七级] 物流网络
编程题
普及+/提高
知识点
题目描述
一个物流网络由 $n$ 个城市和 $m$ 条双向公路组成。每条公路都有两个属性：
- 运输费用 $w_i$
- 景观评分 $b_i$
当一辆运输车从城市 $1$ 运送货物到城市 $n$ 时，需要支付经过道路的运输费用之和。
为了推广旅游线路，物流公司推出了一项优惠政策：在运输路径上，可以**免除景观评分最高**的那条公路的运输费用。如果有多条公路的景观评分同为最大值，则只免除其中 **一条** 的费用。
请你计算，从城市 $1$ 到城市 $n$ 的最小运输费用。
- 运输费用 $w_i$
- 景观评分 $b_i$
当一辆运输车从城市 $1$ 运送货物到城市 $n$ 时，需要支付经过道路的运输费用之和。
为了推广旅游线路，物流公司推出了一项优惠政策：在运输路径上，可以**免除景观评分最高**的那条公路的运输费用。如果有多条公路的景观评分同为最大值，则只免除其中 **一条** 的费用。
请你计算，从城市 $1$ 到城市 $n$ 的最小运输费用。
输入格式
第一行两个整数 $n,m$，分别表示城市数量和公路数量。
接下来 $m$ 行，每行四个整数 $u,v,w,b$，表示存在一条连接城市 $u$ 和城市 $v$ 的双向公路，其中 $w$ 为运输费用，$b$ 为景观评分。
接下来 $m$ 行，每行四个整数 $u,v,w,b$，表示存在一条连接城市 $u$ 和城市 $v$ 的双向公路，其中 $w$ 为运输费用，$b$ 为景观评分。
输出格式
输出一个整数，表示从城市 $1$ 到城市 $n$ 的最小费用。
如果无法到达，输出
如果无法到达，输出
-1。输入输出样例
输入 #1
3 3 1 2 10 5 2 3 20 6 1 3 100 1
输出 #1
0
说明/提示
### 样例解释
路径 $1\to 2\to 3$：费用 $10+20$，最大美丽值 $6$（边 $2-3$）。免除 $20$，总花费 $10$。
路径 $1\to 3$：费用 $100$，最大美丽值 $1$（边 $1-3$）。免除 $100$，总花费 $0$。
### 数据范围
$1\leq n\leq 5000$，$1\leq m\leq 5000$，$1\leq w,b\leq 10^9$。
路径 $1\to 2\to 3$：费用 $10+20$，最大美丽值 $6$（边 $2-3$）。免除 $20$，总花费 $10$。
路径 $1\to 3$：费用 $100$，最大美丽值 $1$（边 $1-3$）。免除 $100$，总花费 $0$。
### 数据范围
$1\leq n\leq 5000$，$1\leq m\leq 5000$，$1\leq w,b\leq 10^9$。