luogu#P5001. 魔法祝福
魔法祝福
题目背景
到了宝塔的大门前,据说塔第层藏了一个惊天的宝藏——dalao的祝福>>(zu zhou),让你NOIP2018 AK>>(bao 0)全场。但以你的智商O__O “…
题目描述
宝塔有层,A向一个dalao购买了魔法,可以从第层跳到第层,也可以从第层跳到层。但每种魔法都有诅咒和一个分值,每使用一次魔法,会用个单位的时间,也就会得到一个诅咒,如果你的诅咒数大于等于这个魔法的分值,那么这个魔法就不能使用了(在这之前魔法无限使用)。的初始诅咒值为-1。 被dalao强制使用了一次魔法(本身不会这个魔法),从第一层跳到了第层(可以是1)。望眼四周,空空如也,没有路。要到达遥远的第层,好像只能编程了吧。输出最少到达所需的时间。如果到天荒地老都到不了,输出“bao 0”(不包含单引号)。
输入格式
第1行,输入4个整数 ,,,(保证≠) 第2行到第+1行,输入4个整数,,,。
输出格式
输出仅一行,输出最小时间或“bao 0”。
5 6 1 5
1 2 5 2
1 3 1 3
2 4 3 2
5 4 1 1
5 3 2 2
3 4 7 5
3
提示
对于 的数据,$ 1 \leq n,p,q \leq 4*10^2,m,k \leq 10^3,t \leq 3*10^2 $;
对于 的数据,$ 1 \leq n,p,q \leq 5*10^3,m,k \leq 10^5,t \leq 10^6 $;
对于 的数据,。