题库 C++/C语言题库 题目列表 青少年C语言等级考试八级真题:道路(roads)。N个以&...
问答题

青少年C语言等级考试八级真题:道路(roads)。

N个以 1  N 标号的城市通过单向的道路相连:。每条道路包含两个参数:道路的长度和需要为该路付的通行费(以金币的数目来表示)

Bob and Alice 过去住在城市 1.在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后,Bob和她分手了,并且决定搬到城市N。他希望能够尽可能快的到那,但是他囊中羞涩。我们希望能够帮助Bob找到从1N最短的路径,前提是他能够付的起通行费。

时间限制:1000

内存限制:65536

 

输入

第一行包含一个整数K, 0 <= K <= 10000, 代表Bob能够在他路上花费的最大的金币数。第二行包含整数N 2 <= N <= 100, 指城市的数目。第三行包含整数R, 1 <= R <= 10000, 指路的数目接下来的R行,每行具体指定几个整数S, D, L  T来说明关于道路的一些情况,这些整数之间通过空格间隔: S is 道路起始城市, 1 <= S <= N D is 道路终点城市, 1 <= D <= N L is 道路长度, 1 <= L <= 100 T is 通行费 (以金币数量形式度量), 0 <= T <=100 注意不同的道路可能有相同的起点和终点。

 

输出

输入结果应该只包括一行,即从城市1到城市N所需要的最小的路径长度(花费不能超过K个金币)。如果这样的路径不存在,结果应该输出-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

 

样例输出

11

题目信息
2022年 八级 编程题 C语言等级考试真题
-
正确率
0
评论
147
点击