Problem 1684. -- [Ceoi1998]Roads

1684: [Ceoi1998]Roads

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 1
[Submit][Status][Web Board]

Description

城市中有R条有向马路,n个马路连接点,通过每条马路都要花去一定费用。你现在在编号为1的连接点
手里有k元钱,要去n号连接点的最短路径的长度是多少?途中经过道路的花费不能超过k。注意:两个
马路连接点间可能有多条马路

Input

第一行,k(0 <= K <= 10000)
第二行,n(2 <= N <= 100)
第三行,R(1 <= R <= 10000
以下R行
x y L t 从x到y的马路,长度L(1<=每条马路的长度<=100),花费t(0<=每条马路的费用<=100)

Output

满足条件最短路长度

Sample Input

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

Sample Output

11
//你可以从1号点走到3号,再走到5号,再走到4号,再走到6号。

HINT

Source

[Submit][Status]