Rescue Jack Sparrow
All submissions for this problem are available.
Will, Elizabeth, Barbossa, and the entire crew of Black Pearl are set out to rescue Captain Jack Sparrow from Davy Jones's Locker. The escape map is a graph with N islands and M routes. Each route represents a bi-directional way from one island to another. The N islands are numbered from 1 to N. With each route associated is end-points (Ai,Bi) and the length of the route Ci. Since Davy Jones have left some of his servants at each island, there is some danger level associated with each island Dj. The crew wants to escape out of the locker of davy jones alive. They need to go from Davy Jone's island to their home following the given routes. As a matter of fact, their ship Black Pearl have only K units of fuel left in it. Black Pearl travels 1 unit with 1 unit of fuel. You need to tell Jack the minimum danger level with which the crew can escape to determine their chances of survival. If it is impossible to escape, the entire crew is doomed and you should print -1. The danger level of a path is defined as the maximum of danger level out of all the nodes present in that particular path.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case would contain two integers, N and K. The following line would contain N integers separated by a single space representing Dj, the danger level of each island. The next line would contain three integers, M, X and Y, representing the number of edges, Davy Jones island and Jack's home respectively. The next M lines contains the routes on the map given by three integers, Ai, Bi and Ci.
For each test case, output a single line containing one integer, the danger level of the required path or -1 if no such path is possible.
- 1 <= N <= 1000
- 1 <= M <= 10000
- 0 <= Ci, K <= 100000
- 0 <= Dj <= 1015
- 1 <= Ai, Bi, X, Y <= N
Input 1 6 10000 20 30 15 5 40 15 8 1 4 1 2 1 2 3 7 3 4 4 4 5 10 6 5 3 6 1 2 2 5 5 3 6 9
|Time Limit:||0.23 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions