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

    编号为 1.. N 的N座城镇用若干仅供单向行驶的道路相连,每条道路上均有两个参数:道路长度(length)和在该条道路上行驶的费用(cost)。
    BOB 准备从城镇 1 出发到达城镇 N,但他目前只有 W 块钱,为此,你需要帮助他寻找一条从城镇1到城镇 N 在他能支付的前提下的一条最短路线。

    输入格式

    第一行为钱的数目W (0<=w<=1000)
    第二行为城镇数目N(2<=N<=100)
    第三行为为道路条数K(1<=K<=10000)
    随后的 K 行每行为一条道路的信息,包含 4个数值(S,D,L,T)其中S为道路的起点, D为道路的终点 , L为道路长度, T为所需支付 费用。
    (1<=S,D<=N,1<=L<=100,0<=T<=100)

    输出格式

    输出最短长度,若无解,则输出“NO”;

    样例输入




    1 2 2 3 
    2 4 3 3 
    3 4 2 4 
    1 3 4 1 
    4 6 2 1 
    3 5 2 0 
    5 4 3 2 

    样例输出

    11


    来源  CEOI1998