Minimum Time in Wormhole Network
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).

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

Question

Minimum Time in Wormhole Network

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).

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

Accepted Answer

Approach(Using Djikstra's 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.

TC : O(N^2), where N is the number of vertices which is equal to 2*(Number of wormholes+2)
SC : O(N^2)

Accepted Answer

Djikstra algorithm

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.
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.
Now, we need to update the time according to wormholes.
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.
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

Space Complexity: O(1)Explanation:

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

Time Complexity: O(1)Explanation:

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)