Batman and Kryptonite
All submissions for this problem are available.
With the help of Harley Quinn, Batman has discovered a new place where he can get Kryptonite to defeat Superman. This new place has N site s(numbered from 0 to N-1).There is an entry site(numbered 0) from which every other site is accessible. Batman can get a block of Kryptonite of some specific weight at every site except the entry site. There are paths between sites which take some time to travel. Even though, Batman has trained very hard, he can still carry only one block of Kryptonite at a time. Robin is waiting at the entry gate with the Batmobile ready. What Batman does is, he takes a block of Kryptonite and takes it to his Batmobile and then goes for another block. But, Batman has some specific time before Superman comes and stops him. Batman wants to maximise the amount of Krytonite he can gather in the little time he has. Since, Batman does not have WB excutives to help him, he has asked you to solve this problem for him.
First line contains T ,the number of test cases.
- Second line contains three space seperated integers N, M and D, Number of sites, Number of paths and time Batman has.
- Then follow m lines. Each line will contain three space seperated integers u v e denoting that there is a path from site u and v which take e seconds to travel.
- Last line contains N-1 space seperated integer W[i] denoting the weight of kryptonite at the ith site.(1<=i<=N-1)
For each test case
- Output the maximum amount of Krytonite he can gather in the given time in a newline.
- 1 <= T <= 20
- 2 <= N <= 10^4
- N-1 <= M <= 10^5
- 1 <= W[i] <= 10^6
- 0 <= u < N
- 0 <= v < N
- 1 <= e <= 10
- 1 <= D <= 1000
Input: 1 7 6 20 0 1 3 0 2 2 2 3 3 0 4 6 4 5 1 5 6 1 1 1 7 1 19 100 Output: 101
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions