All submissions for this problem are available.
Cars of future no longer need fuel to run, but they are fitted with special engines which can only operate in one of the two modes at a time ,either go up the road, or go down the road.
There are N towns in country. ith town is at height H[i] (1 ≤ i ≤ N) above the sea level.
Changing mode of the car requires permissions from mayor of the town you are currently at. Mayor of ith town charges amount C[i] (1 ≤ i ≤ n) for giving permission to change mode of the car.
These N towns are connected by R bidirectional roads. Initially no mode is set, so you need permissions to set a mode.
You have to travel from town 1 to N, in minimum amount of cost. Print minimum money required to make the travel. If it is impossible print -1.
- Go up the road mode: when you are at town A and want to go to town B, where H[A] <= H[B]
- Go down the road mode: when you are at town A and want to go to town B, where H[A] >= H[B]
- If you continue with the same mode, you do not need to take permissions from mayor.
- First line contains two space separated integer N and R, number of towns and number of roads.
- Next line contains N space separated integer where ith integer is H[i], height of ith town.
- Next line contains N space separated integer where ith integer is C[i], cost charged by mayor of ith town to give permission for changing the mode.
- Next R lines contains two space separated integer u and v, specifying there is a bidirectional road between town u and v.
Print minimum cost required for travel. If it is impossible print -1.
- 2 ≤ N ≤ 100000
- 1 ≤ R ≤ 500000
- 1 ≤ H[i] ≤ 109
- 1 ≤ C[i] ≤ 109
Input: 6 6 10 5 7 15 20 6 1 1 1 1 1 1 1 2 2 3 3 6 1 4 4 5 5 6 Output: 2
There are two paths from 1 - 6
P1: (1, 2, 3, 6)
You need to pay $1 to mayor of town 1 to chose down mode. (H >= H)
You need to pay $1 to mayor of town 2 to chose up mode. (H <= H) You need to pay $1 to mayor of town 3 to chose down mode. (H >= H)
Total cost = $3
P2: (1, 4, 5, 6)
You need to pay $1 to mayor of town 1 to chose up mode. (H <= H)
You continue with the previous up mode. (H <= H)
You need to pay $1 to mayor of town 5 to chose down mode. (H >= H)
Total cost = $2
So minimum money required is $2.
|Tags||amanmittal, dijkstra, fcar, insq2015|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, TEXT, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.