SDE - 1

There is a source (S) and destination (D) and a spacecraft has to go from S to D. There are N number of wormholes in between which has the following properties:

Each wormhole has an entry and an exit.

Each wormhole is bi-directional i.e. one can enter and exit from any of the ends.

The time to cross the wormhole is given and the space craft may or may not use the wormhole to reach D.

The time taken to travel outside wormhole between two points (x1, y1) and (x2, y2) is given by a formula

|x1 - x2| + |y1 - y2|

where, (x1, y1) and (x2, y2) are the co-ordinates of two points.

The co-ordinates of S and D are given and we have to find the minimum time to reach D from S.

Note: It’s not mandatory to consider all the wormholes.

Find maximum possible stolen value from houses

There are n houses build in a line, each of which contains some value in it. A thief is going to steal the maximal value of these houses, but he can’t steal in two adjacent houses because the owner of the stolen houses will tell his two neighbours left and right side. What is the maximum stolen value?

Examples:

Input: hval[] = {6, 7, 1, 3, 8, 2, 4}

Output: 19

Explanation: The thief will steal 6, 1, 8 and 4 from the house.

Input: hval[] = {5, 3, 4, 11, 2}

Output: 16

Explanation: Thief will steal 5 and 11