问题 23811 --乘车路线

23811: 乘车路线

时间限制: 1 Sec  内存限制: 128 MB
提交: 325  解决: 47
[提交][状态][讨论版][命题人:]

题目描述

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

输入

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

输出

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

样例输入

6 7 5
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

来源

 

[提交][状态]