描述

東非大裂谷中有一片神秘的叢林，是全世界探險家的樂園，著名黃皮膚探險家BB一直想去試試。正好我國科學家2005年4月將首次對東非大裂谷進行科考，BB決定隨科考隊去神秘叢林探險。在出發之前，他搜集了國內外有關神秘叢林探險的資料，并繪制成一張地圖：該地圖上有若干安全點（包括入口點和出口點），并將這些安全點編號為1、2、…、n；如果一個安全點和另一個安全點有一條路直接相通，則用一條邊標示；該圖是一個連通圖（任意兩點間有至少一條路徑），地圖上每條路的長度和走這條路需要耗費的體力都做了標示。

KK行走速度為1，并知道自己體力為K。他想知道根據自己的體力情況能否成功地穿過叢林。

格式

輸入格式

第一行兩個整數n（<=5000） m（<=40000），分別表示地圖上安全點的個數和邊的數目；
第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

樣例1

樣例輸入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 Copy

樣例輸出1

11 Copy

限制

各個測試點1s

轉載于:https://www.cnblogs.com/zzqc/p/7056671.html

總結

以上是生活随笔為你收集整理的vijos 1082的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。