问题 24778 --【USACO2014OPEN】导航竞争{silver题2}

24778: 【USACO2014OPEN】导航竞争{silver题2}

时间限制: 5 Sec  内存限制: 256 MB
提交: 6  解决: 4
[提交][状态][讨论版][命题人:]

题目描述

导航竞争{silver题2} 

【问题描述】

农民约翰的汽车安装的两个导航仪在选择路线时经常出现冲突。

他居住区域的地图上有N(2 <= N <= 10,000)个结点和M(1 <= M <= 50,000)条有向边,边i连接节点A_i (1 <= A_i <= N) 和 B_i (1 <= B_i <= N)。两个结点之间可能有多条有向边。约翰的家住在结点1,他的农场在结点N。

两个导航仪使用同一份地图,但是对一同一条边,他们标注为不同驾驶时间。对于边i, i第一个导航仪标注P_i的时间,第二个导航仪标注Q_i的时间,皆为[1..100,000]的整数。

约翰开车从家里出发去他的牧场,每当他经过一条边的时候,比如从结点X到结点Y,若某个导航仪认为这不是从结点X到农场的最短路径上的一部分的时候,就会产生抱怨。若两个导航仪都不认为,则都会产生抱怨。

请帮助约翰找到一条合适的路径,使得在他的行程中,两个导航仪抱怨的次数最少。若在经过某条边时,两个导航仪均抱怨,则抱怨次数加2。

【文件输入】gpsduel.in

第一行两个整数N和M。

接下来M行,每行四个整数,分别表示A_i, B_i ,P_i, Q_i。

【文件输出】gpsduel.out

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

【输入样例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

 

【样例1说明】

如果约翰选择的路径是1 - >2 - >4 - >5,则第一导航抱怨1 - >2路(它宁愿用1 - >3路代替)。对于其余的2 - >4 - >5,这两个导航都不会抱怨。


 

来源

 

[提交][状态]