Minimum Time in Wormhole Network

Hard
0/120
Average time to solve is 44m
profile
Contributed by
26 upvotes
Asked in companies
SamsungNagarro Software

Problem statement

You will be given a starting point (sx, sy) and a destination point (dx, dy) in the two-dimensional coordinate system representing the universe.

Your spacecraft can move only in X(left or right) or Y(up or down) direction, and not in the diagonal direction. To go from one point (x1, y1) to another point (x2, y2), total time taken is |x2 - x1| + |y2 - y1| seconds.

Also, in this two-dimensional system, N wormholes are present. If you go through a wormhole, spacecraft will take some time to travel from the entry of the wormhole to its exit point. You have to find out the minimum time in which you can go from the source to the destination.

What is a Wormhole?

A wormhole is a sort of tunnel that joins distant points in space, or even two universes, via space-time curvature. Theoretically, such a tunnel could be traversed from one point in space to another without actually travelling the distance between them.
Note: 
1. Endpoints of all the wormholes are pairwise distinct.
It means if a wormhole starts or ends at the coordinate (x, y) then no other wormhole will start or end from the same coordinate. This holds true for the source and the destination coordinates as well.

2. If your path intersects with the wormhole, your spacecraft won't get sucked into the wormhole.  As soon as you reach the entry/exit point of a wormhole you will come out from the exit/entry point( Wormholes are bi-directional).
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line contains 4 space-separated integers sx, sy, dx and dy where (sx, sy) is the source point and (dx, dy) is the destination point.

The second line contains an integer N representing the number of wormholes.

From the third line, N lines contain five space-separated integers where the first two integers represent the starting point of wormhole next two integers represent the exit point of the wormhole and the fifth integer represents the time taken if this wormhole is used.
Output format : 
The only line of output print the minimum time in which you can travel from the source to the destination point.
Constraints : 
1 <= Coordinates <= 10^5
1 <= N <= 200
1 <= Wormhole Time <= 10^5

Time Limit: 1 sec
Sample Input 1:
0 0 10 10
0
Sample Output 1:
20
 Explanation for Sample Input 1:
As there are no wormhole you will need to go the destination directly so the time taken = |10 - 0| + |10 - 0| = 20.
Sample Input 2:
0 0 20 20
2
2 2 10 10 5
8 8 16 16 5
Sample Output 2:
26
 Explanation for Sample Input 2:
First, go from the source to the first wormhole, it will take |2 - 0| + |2 - 0| = 4 unit of time. Since you have reached a starting point of a wormhole your spacecraft will get sucked into it and you will reach (10,10) with the time consumption of 5. So total time till now is 5 + 4 = 9.
Now, from (10,10) go to the start point of second wormhole with the time = |8 - 10| + |8 - 10| = 4. Now using this wormhole you will reach (16,16) with the time  = 5. So total time till now is 9 + 4 + 5 = 18. From here go to the destination with the time = |20 - 16| + |20 - 16| = 8. 
So the total time consumed = 18+8 = 26. You can not reach the destination with the time less than this.
Hint

Can you convert the given problem into a graph using the vertices of wormholes? If you have a graph do you know any algorithm to find the shortest distance?

Approaches (1)
Djikstra algorithm
  1. Mark the source point as vertex 0, destination point as vertex 1 and all the wormholes are formed with start point and endpoint so similarly mark the start point as next vertex number 2 and endpoint as next vertex number 3 and so on.
  2. Now create a complete graph using adjacency matrix which will store the time to reach from vertex i to vertex j (Calculated using the given formula in the description). This graph contains the time without considering any wormhole.
  3. Now, we need to update the time according to wormholes.
  4. Since we know that if we reach the start/end point of a wormhole we must use it (we can't bypass the wormhole), so we change the time for all the wormholes to the time given for the wormholes in the input without any other check.
  5. Now, we need to apply the Dijkstra algorithm to find minimum time from source to destination in this graph.

    If you want to read about Dijkstra algorithm, view it here : 
    https://www.youtube.com/watch?v=7GoDDj3onfI 

 

Time Complexity

O(N^2), Because we are running two nested loops of size equal to the number of vertices. Where N is the number of vertices which is equal to 2*(Number of wormholes+2)

Space Complexity

O(N^2), Because we are creating a 2-dimensional matrix of size N*N.

Code Solution
(100% EXP penalty)
Minimum Time in Wormhole Network
Full screen
Console