logo AlgoBeat OnlineJudge
登录 注册

#215860. [GESP202603 七级] 物流网络

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

对应的选择、判断题:https://ti.luogu.com.cn/problemset/1211


一个物流网络由 个城市和 条双向公路组成。每条公路都有两个属性:

  • 运输费用
  • 景观评分

当一辆运输车从城市 运送货物到城市 时,需要支付经过道路的运输费用之和。

为了推广旅游线路,物流公司推出了一项优惠政策:在运输路径上,可以免除景观评分最高的那条公路的运输费用。如果有多条公路的景观评分同为最大值,则只免除其中 一条 的费用。

请你计算,从城市 到城市 的最小运输费用。

输入格式

第一行两个整数 ,分别表示城市数量和公路数量。

接下来 行,每行四个整数 ,表示存在一条连接城市 和城市 的双向公路,其中 为运输费用, 为景观评分。

输出格式

输出一个整数,表示从城市 到城市 的最小费用。

如果无法到达,输出 -1

样例

样例输入 1

3 3
1 2 10 5
2 3 20 6
1 3 100 1

样例输出 1

0

数据范围与提示

样例解释

路径 :费用 ,最大美丽值 (边 )。免除 ,总花费

路径 :费用 ,最大美丽值 (边 )。免除 ,总花费

数据范围