#P3720. [AHOI2017初中组] guide

[AHOI2017初中组] guide

题目描述

农场主John最近在网上买了一辆新车,在购买汽车配件时,John不小心点了两次“提交”按钮。导致汽车上安装了两套GPS系统,更糟糕的是John在使用GPS导航时,两套系统常常给出不同的路线。从地图上看,John居住的地区有N(2 ≤ N ≤ 100,000)个十字路口和M(1 ≤ M ≤ 500,000)条限定通行方向的道路。第i条道路连接路口 A_i (1 ≤ A_i ≤ N)和B_i (1 ≤ B_i ≤ N),两个路口之间可能连接有多条道路。允许双向通⾏的道路是将两条单向通⾏的道路隔开所形成的。

John的家在路口1位置,农场在路口N的位置。John可以沿着⼀系列单向道路从家驾车到农场。所有GPS系统的底层地图信息都是⼀样的,区别仅在于对每一条道路的通⾏时间计算不同。对于第i条道路第一套GPS系统计算通行时间为P_i个单位时间,而第二套GPS系统则给出Q_i个单位时间。(所有道路的通行时间都是范围在1到100,000之间的整数)John想要驾车从家到农场。可是,一路上GPS系统总是不厌其烦的提醒John(请从路口X开往路口Y),这是由于John选取了某套GPS系统建议的路径,而另一套GPS系统则认为这不是从路口X到农场的最短路径。我们称之为GPS系统的抱怨。

请你计算一下如果John选择合适的路径到达农场能听到的最少GPS系统的抱怨数 。如果John经过某条道路两套GPS系统都发出抱怨,则抱怨总数加2。

输入格式

第一行,两个整数N和M。

接下来M行,其中第i行描述了道路i的信息,A_i B_i P_i Q_i。

输出格式

一个整数,表示John一路上能听到的最小抱怨数。

5 7 3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 5
1