1461: 天空城
Memory Limit：256 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：39
Solved：14
Description
褪色者骑着古龙弗尔桑克斯想要到达天空城,然而古龙受了伤只有 $k$ 点护甲值,如果古龙护甲值为0,那么他们将会坠落.
有 $n$ 个天空岛,编号为 $1∼n$
有 $m$ 条双向道路,古龙只能沿着道路飞行,其中第 $i$ 条道路直接连接两个不同的岛屿 $u_i$ 和 $v_i$ ,该道路的飞行时长为 $t_i$ ，经过该航线会使得古龙的护甲磨损 $h_i$ 点.
一对岛屿之间可能有多条道路直接相连.
我们希望从起点 $S$ 出发到达天空城 $T$
首先,我们必须保证古龙能够顺利抵达,这意味着飞行线路必须保证护甲磨损的总和必须严格小于k.
另外,我们还希望在确保古龙能顺利抵达的前提下,沿途花费的时间尽可能小.
请你计算并输出,在确保古龙能安全抵达的前提下，沿途所需花费的最短总时间.
有 $n$ 个天空岛,编号为 $1∼n$
有 $m$ 条双向道路,古龙只能沿着道路飞行,其中第 $i$ 条道路直接连接两个不同的岛屿 $u_i$ 和 $v_i$ ,该道路的飞行时长为 $t_i$ ，经过该航线会使得古龙的护甲磨损 $h_i$ 点.
一对岛屿之间可能有多条道路直接相连.
我们希望从起点 $S$ 出发到达天空城 $T$
首先,我们必须保证古龙能够顺利抵达,这意味着飞行线路必须保证护甲磨损的总和必须严格小于k.
另外,我们还希望在确保古龙能顺利抵达的前提下,沿途花费的时间尽可能小.
请你计算并输出,在确保古龙能安全抵达的前提下，沿途所需花费的最短总时间.
Input
第一行包含三个整数 $k,n,m$
接下来$m$行,每行包含四个整数 $u_i,v_i,t_i,h_i$ 用来描述一条双向道路.
最后一行,包含两个整数 $S,T$ 分别表示起点和终点
数据范围:$1\leq k \leq200$
$2\leq n \leq2000$
$1\leq m \leq10000$
$1\leq u_i,v_i \leq n$
$u_i\neq v_i$
$1\leq t_i\leq 1e5$
$0\leq h_i \leq 200$
$1\leq S,T \leq n$
$S\neq T$.
接下来$m$行,每行包含四个整数 $u_i,v_i,t_i,h_i$ 用来描述一条双向道路.
最后一行,包含两个整数 $S,T$ 分别表示起点和终点
数据范围:$1\leq k \leq200$
$2\leq n \leq2000$
$1\leq m \leq10000$
$1\leq u_i,v_i \leq n$
$u_i\neq v_i$
$1\leq t_i\leq 1e5$
$0\leq h_i \leq 200$
$1\leq S,T \leq n$
$S\neq T$.
Output
一个整数,表示在确保古龙能安全抵达的前提下,沿途所需花费的最短总时间.
如果古龙无法安全抵达,则输出$-1$.
如果古龙无法安全抵达,则输出$-1$.
Sample Input Copy
10 4 7
1 2 4 4
1 3 7 2
3 1 8 1
3 2 2 2
4 2 1 6
3 4 1 1
1 4 6 12
1 4Sample Output Copy
7