#P3538. [Usaco2014 Open]Dueling GPS

    ID: 2748 传统题 1000ms 128MiB 尝试: 288 已通过: 150 难度: 4 上传者: 标签>难度分类普及+/提高-图论反图求到终点距离DijkstraCF1600SilverByliyizhen2

[Usaco2014 Open]Dueling GPS

[USACO14OPEN] Dueling GPSs S

题目描述

农夫约翰的车上有两套 GPS。地图上有 NN 个路口、MM 条单向道路。第 ii 条道路从 AiA_i 通往 BiB_i,两套 GPS 分别认为通过该道路需要 Pi,QiP_i,Q_i 个单位时间。可以有重边,双向通行用两条方向相反的道路表示。

约翰要从家所在的路口 11 开到农场所在的路口 NN。每进入一条从 XX 到 YY 的道路,若这条道路无法作为从 XX 到农场的任意一条最短路线的第一条道路,则按相应时间计算的那套 GPS 会抱怨一次。两套 GPS 分开判断,同一条道路可引起两次抱怨。

求约翰从家到农场的所有合法路线中,抱怨总次数的最小值。保证至少有一条路线。

输入格式

第一行两个整数 N,MN,M。接下来 MM 行,每行四个整数 Ai,Bi,Pi,QiA_i,B_i,P_i,Q_i。

输出格式

一行一个整数,表示最少抱怨次数。

样例 #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

选择 1→2→4→51\to2\to4\to5。第一套 GPS 在 1→21\to2 这一步抱怨,其余两步都可作为各自当前位置的最短路线的一部分,两套 GPS 均不抱怨。

数据范围

2≤N≤1042\le N\le10^4,1≤M≤5×1041\le M\le5\times10^4,1≤Ai,Bi≤N1\le A_i,B_i\le N,1≤Pi,Qi≤1051\le P_i,Q_i\le10^5。