The Empire Strikes Back
All submissions for this problem are available.
You are a young spy in the army of the Jedi, posted on the outer rim of the Tatooine. You learn that Darth Vader’s army is on the way to attack the Planet. You want to save Tatooine and you need help of the Jedi Council to defeat the army of Darth Vader. To seek Jedi help you have to inform the Jedi Council sitting at the Jedi Temple which is very far from where you are.
You have a pod with you which runs on electricity and you would like to use it to travel to the Jedi Temple. But the battery of your pod lasts for only a fixed amount of time, C. There are many service stations on your way from the outer rim to the Jedi Temple and luckily for you, some of these allow you to recharge your pod’s battery.
You are in a hurry and want to reach the Jedi Temple in as little time as possible. If you are late, then it might be impossible to save the peaceful planet of Tatooine from the dark forces of Darth Vader’s army. Given the time needed to travel between the service stations, you are asked to output the minimum time in which you would be able to reach the Jedi Temple.
The first line of each input contains four space separated integers, N M P C where
- N: The number of service stations including 0 for the starting point and N-1 as the location of the Jedi Temple.
- M: The number of 1-length paths existing between pairs of N service stations
- P: The number of service stations which allow you to recharge your battery
- C: The maximum time for which your battery runs, after you had charged it completely
The next line contains P space separated integers denoting the service stations which allow you to recharge.
This is followed by M lines, each containing three space separated numbers X Y T
where T is the time required to travel between X and Y
Assume that the initial charge in the pod is 0 and it takes negligible time to recharge your battery at the service stations (After all, being in Jedi army has its perks ;) ).
Output a single integer t which is the time required to travel from your initial position to the Jedi Temple. If it is not possible for you to reach the Jedi temple, print -1.
- 1 ≤ N ≤ 300
- 1 ≤ M ≤ min(n*(n-1)/2, 5*104)
- 1 ≤ P ≤ N
- 1 ≤ C ≤ 107
- 0 ≤ X ≤ N-1
- 0 ≤ Y ≤ N-1
- 0 ≤ T ≤ 104
Input: 6 5 2 250 0 4 0 1 200 1 2 30 2 3 10 3 4 10 2 5 230 Output: 500
|Time Limit:||0.610687 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, GO|
Fetching successful submissions