1074. 丛林探险

时间限制 1000 ms
内存限制 128 MB

题目描述

东非大裂谷中有一片神秘的丛林,是全世界探险家的乐园,著名黄皮肤探险家BB一直想去试试。正好我国科学家2005年4月将首次对东非大裂谷进行科考,BB决定随科考队去神秘丛林探险。在出发之前,他搜集了国内外有关神秘丛林探险的资料,并绘制成一张地图:该地图上有若干安全点(包括入口点和出口点),并将这些安全点编号为1、2、…、n;如果一个安全点和另一个安全点有一条路直接相通,则用一条边标示;该图是一个连通图(任意两点间有至少一条路径),地图上每条路的长度和走这条路需要耗费的体力都做了标示。
KK行走速度为1,并知道自己体力为K。他想知道根据自己的体力情况能否成功地穿过丛林。

输入数据

第一行两个整数 $n\ (\le 5000) m\ (< 4\times10^{3}),$ 分别表示地图上安全点的个数和边的数目;
第 $2$ 行至第 $m+1 $ 行每行 $4$ 个整数 $x y c d, x, y$ 表示有直接相联边的两个点的编号 $,c$ 走这条路需要耗费的体力 $; d$ 表示边的长度;(其中150< =c,d< =300)
第 $m+2$ 行两个整数 $s t,$ 分别表示安全的入口点和出口点的编号;
第 $m+3$ 行一个整数 $k,$ 表示 $BB$ 的体力值 $; \ (K< 10^{9})$
同一行上的多个数据用空格隔开。

输出数据

一个整数,如果 $BB$ 能安全地从如入口穿过丛林到达出口,输出最短时间,否则输出 $-1 $

样例输入

4 5
1 2 2 3
1 3 3 5
1 4 7 10
2 4 4 6
3 4 2 6
1 4
5

样例输出

11

题目信息

未提交
未通过无法查看
未通过无法查看