#P3538. [Usaco2014 Open]Dueling GPS
[Usaco2014 Open]Dueling GPS
[USACO14OPEN] Dueling GPSs S
题目描述
农夫约翰的车上有两套 GPS。地图上有 个路口、 条单向道路。第 条道路从 通往 ,两套 GPS 分别认为通过该道路需要 个单位时间。可以有重边,双向通行用两条方向相反的道路表示。
约翰要从家所在的路口 开到农场所在的路口 。每进入一条从 到 的道路,若这条道路无法作为从 到农场的任意一条最短路线的第一条道路,则按相应时间计算的那套 GPS 会抱怨一次。两套 GPS 分开判断,同一条道路可引起两次抱怨。
求约翰从家到农场的所有合法路线中,抱怨总次数的最小值。保证至少有一条路线。
输入格式
第一行两个整数 。接下来 行,每行四个整数 。
输出格式
一行一个整数,表示最少抱怨次数。
样例 #1
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
选择 。第一套 GPS 在 这一步抱怨,其余两步都可作为各自当前位置的最短路线的一部分,两套 GPS 均不抱怨。
数据范围
,,,。