2164. Unhappy

单点时限: 2.0 sec

内存限制: 256 MB

McFn 和女朋友 Bonbon 吵架了,他现在心情很不好。所以他开着自己的小 QQ,打算到他好朋友 Toksky 和 Haozi 所在的城市散心。他想见他的朋友,越快越好。他现在有一张地图 , 地图上有 N 个城市,用 1…N 的数字标号。地图上有 M 条道路,每条道路连接两个城市,而却都是单向的,与此同时,每条道路都有一个收费站,你要经过它就必须交一定金额的过路费。但是小 A 身上的钱有限,McFn 数学很强,但是他现在脑子很乱,想让你帮忙解决这个问题 : 在他资金能够承受的范围内,帮他寻找一条从城市 1 到城市 N 的一条最短路径。

输入格式

第一行有一个整数 T (1<=T<=20),表示测试数据总数

每组 case 的第一行是一个整数 K, 表示 McFn 身上的钱的总数。(0<=K<=10000)

第二行是一个整数 N(1<=N<=100) 表示城市总数

第三行是一个整数 M(1<=M<=10000) 表示道路的总数

接下来的 M 行,每行有四个用空格间开的整数 S,D,L,C

S 表示起点城市,(1<=S<=N)

D 表示终点城市 ,(1<=D<=N)

L 表示道路的长度 (1<=L<=100)

C 表示经过该道路所需的过路费 (0<=C<=100)

输出格式

对于每组数据输出一行,输出 McFn 能走的从城市 1 到城市 N 的最短路径的总长度。如果该路径不存在,输出-1。

样例

Input
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
Output
11

5 人解决,22 人已尝试。

11 份提交通过,共有 133 份提交。

8.8 EMB 奖励。

创建: 13 年,11 月前.

修改: 4 年,10 月前.

最后提交: 9 年,2 月前.

来源: DLL

题目标签