TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3056
  • 题目
  • P3056导航
    限制 : 时间限制 : 10000 MS   空间限制 : 131072 KB
    问题描述

    约翰在他的新车上装了两个导航系统(GPS),但这两个GPS选择的导航线路常常不同,约翰很是恼火。
    约翰所在的小镇地图由N个路口和M条单向道路构成,两个路口间可能有多条道路相连。约翰的家在1号路口,他的农场在N号路口。约翰从家出发,可以经过一系列的道路,最终到达农场。
    两个GPS用的都是上述地图,但是,它们计算时间的算法不同。比如,经过第i条道路,1号GPS计算出的时间是Pi分钟,而2号GPS算出的时间是Qi分钟。
    约翰想要驾车从家到农场,但是,如果一个GPS认为约翰当前行走的这条路不在它算出的最短路径中,该GPS就会大声抱怨约翰走错了路(每个GPS会算出所有最短路,只要你在其中一条上最短路上它都不会抱怨)。更倒霉的是,有可能两个GPS会同时抱怨约翰当前走的路不是它们推荐的。
    请帮助约翰计算,从家到农场过程中,选择怎样的路径才能使得GPS抱怨的次数最少,请算出这个最少的抱怨次数。如果一条路上两个GPS都在抱怨,算两次(+2)抱怨。

    输入格式

    第1行两个空格间隔的整数,N和M
    接下来M行,每行描述一条道路。第i行描述第i条道路,由四个空格间隔的整数构成,Ai,Bi,Pi,Qi,分别表示该条道路的起点、终点、1号GPS计算的耗时、2号GPS计算的耗时。

    输出格式

    一个整数,表示所求答案。

    样例输入

    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->5,1号GPS会在1->2抱怨(它会推荐走1->3这条路)。
    但是,剩下的路径2->4->5,两个GPS都不会抱怨, 因为它们算出的从2到5最短路径都是走这条路。

    数据范围:
    对于30%的数据,1<=N<=20,1<=M<=20
    对于100%的数据,1<=N<=10000,1<=M<=50000,0<=Pi,Qi<=100000


    来源  感谢nodgd放题