All submissions for this problem are available.
Aseem is from a wizarding family. His girlfriend (I forgot her name again :/ ), got selected for attending Hogwarts school of Witchcraft and Wizardry. Now its his duty (and pleasure ;) ) to accompany her though diagon alley while she picks up all the items needed for her first year at school. The diagon alley is a straight street (a single lane) with shops lined up at integer distances from the entrance. They enter the diagon alley through the Leaky couldron and in the end, after picking up all the required items, he plans to take her to Florean Fortesque's ice cream parlour for a date.
To pick up all the items, there are N shops they need to visit. You are given an array dist(array is 1-indexed) of size N denoting the distance of the ith shop from the entrance. The elements of this array are strictly increasing, i.e., dist[i] < dist[j] (i < j).
There are some dependencies on the order in which the shops can be visited. You have to visit the shop with index a before the shop with index b (a > b, remember shops are 1-indexed). Finally,after all the items have been picked, Aseem takes her to Florean Fortesque's, which is at a distance, D from the entrance.
Aseem wants to minimise the total distance travelled so that they can spend more time on their date.
The first line contains 3 space- separated integers, N, M and D.
The next line contains N space-separated integers denoting the array dist. It is guaranteed that this array is sorted in strictly increasing order.
The next M lines contain 2 integers each, a and b. The shop with index a must be visited before the shop with index b. It is guaranteed that a is strictly greater than b.
Output a single integer, denoting the minimum distance travelled.
- 1 <= N <= 10^5
- 0 <= M <= 10^5
- 1 <= each element of dist, D <= 10^9
Input1: 10 3 100 9 14 16 21 34 45 56 64 75 98 9 6 5 2 5 4 Output1: 200 Input2: 1 0 5 10 Output2: 15
|Tags||deathsurgeon, easy, implementation, ipc15amr|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, PAS fpc, PAS gpc, RUBY, PHP, 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