luogu#P5001. 魔法祝福

    ID: 9025 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>SPFA图论最短路贪心递归邻接表

魔法祝福

题目背景

A A 到了宝塔的大门前,据说塔第q q 层藏了一个惊天的宝藏——dalao的祝福>>(zu zhou),让你NOIP2018 AK>>(bao 0)全场。但以你的智商O__O “…

题目描述

宝塔有n n 层,A向一个dalao购买了魔法,可以从第x x 层跳到第y y 层,也可以从第y y 层跳到x x 层。但每种魔法都有诅咒和一个分值k k ,每使用一次魔法,会用t t 个单位的时间,也就会得到一个诅咒,如果你的诅咒数大于等于这个魔法的分值k k ,那么这个魔法就不能使用了(在这之前魔法无限使用)。A A 的初始诅咒值为-1。 A A 被dalao强制使用了一次魔法(A A 本身不会这个魔法),从第一层跳到了第p p 层(p p 可以是1)。望眼四周,空空如也,没有路。要到达遥远的第q q 层,好像只能编程了吧。输出最少到达所需的时间。如果到天荒地老都到不了,输出“bao 0”(不包含单引号)。

输入格式

第1行,输入4个整数n n m m p p q q (保证p p q q ) 第2行到第m m +1行,输入4个整数x x y y t t k k

输出格式

输出仅一行,输出最小时间或“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

提示

对于 20% 20\% 的数据,$ 1 \leq n,p,q \leq 4*10^2,m,k \leq 10^3,t \leq 3*10^2 $;

对于 50% 50\% 的数据,$ 1 \leq n,p,q \leq 5*10^3,m,k \leq 10^5,t \leq 10^6 $;

对于 100% 100\% 的数据,1n,p,q106,m,k106,t108 1 \leq n,p,q \leq 10^6,m,k \leq 10^6,t \leq 10^8