中文
日本語
English
| P5920导航路线 | ||
|
问题描述
何老板打算开车从1号城市出发去N号城市 。
他打开手机地图，想找一条合适的路线。 地图上显示共N座城市（编号1到N）由M单向道路相连，每条道路上均显示有两个信息：通过该道路所需的时间和在该道路上行驶所需的过路费。
何老板想尽快到达终点，但他只有K块钱，为此，他需要寻找一条从城市1到城市N在他能支付的前提下的所需时间最少的路线。请你帮他导航！
输入格式
第一行一个整数K
第二行一个整数N
第三行一个整数M
随后的 M 行每行描述一条道路，包含 4个整数（X,Y,L,T），分别是道路的起点， 道路的终点，通过该道路所需时间， 通过该道路所需支付的费用。
输出格式
一个整数，表示所需最短时间，若无解，则输出“NO”；
样例输入 1
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
样例输出 1
11
样例输入 2
15
12
16
1 8 20 0
1 2 10 0
2 8 5 0
1 7 100 0
2 3 5 1
3 4 5 1
4 5 5 1
5 6 5 1
6 12 5 1
8 12 10 20
8 9 1 1
9 10 1 1
10 11 1 1
11 7 2 10
7 12 10 1
11 4 1 0
样例输出 2
30
提示
对于100%的数据 1 ≤ N ≤ 100 ，1 ≤ K ≤1000 ，1 ≤ M ≤10000 1 ≤ X,Y ≤N ， 0 ≤ L,T ≤100