Problem D: 自驾游

"
Time Limit $2$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $441$ 正确数量 $119$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 图论

P省有N个城市,编号分别为1..N,烦烦家住 1号城市,N号城市是省会,P省的交通非常发达,有M条有向的高速公路连接这N个城市,第i条高速公路(1<=i<=M)从城市ui连向城市vi。

这天,烦烦想自己开车从家前往省会城市游玩.烦烦是个做事很细致的人,为了有备无患,她决定同时开着heroMap和amap这两个不同的导航软件来帮助白已完成这次旅程,这两个导航软件内部采用了不同的算法,对于第i条高速公路(1<=i<=M),heromap 认为通过时间为Pi分钟,amap 则认为通过时间为Qi分钟。这两个导航软件会根据自己的数据来计算从当前位置到目标位置所需的短时间是多少,对于第i个城市(1<=i<=N),记heromap认为从i到N把时间为heor(i),记amap认为到i到N的最短时间为a(i)。烦烦开车途经某条高速公路(1<=i<=M)时,如果heromap认为从ui到N不应该走这条路,即hero(vi)+Pi>hero(ui),则发出一次警告,同样的,如果amap认为从ui到N不应该走这条路,即a(vi)+Qi>a(ui),也会发出一次警告。

现在烦烦希望自己选择选择一条路径,使得收到的警告总数最少,请你编程解决这一问题。

第一行是两个整数N和M。N表示城市数目,M表示连接N个城市的公路数。

接下来M行,第i行有四个整数ui,vi,Pi,Qi,分别表示第i条边的出发点和到达点编号,两个导航软件认为走这条边所用的时间。

2<=N<=10,000

1<=M<=50,000

1<ui,vi<=N

输出从1走到N最少收到多少次警告

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