I have a problem with a 2D grid, where you are trying to find the shortest path from (0, 0) to (N, N), where 1 < N < 10^9. There are also P (1 < P < 10^5) shortcuts, where you can jump from (x1, y1) to (x2, y2).

When you travel, you can only walk up or to the right. Similarly the shortcuts will never move you down or to the left.

Sample case:
You are at (0, 0) and are trying to reach (3, 3).
There are two shortcuts: one moves you from (0, 1) to (0, 2), and one moves you from (1, 2) to (2, 3).

The best path is:

Move from (0,0) to (0,1) (1 unit).
Shortcut to (0,2).
Move from (0,2) to (1,2) (1 unit).
Shortcut to (2,3).
Move from (2,3) to (3,3) (1 unit).

So the total length would be 3 units.

The time frame is also 2 seconds.

EDIT 1: I had the idea to use dynamic programming, to do a cost matrix. The matrix[i][j] = total cost of path to reach (i, j). However, the grid is huge and the matrix would have 10^18 slots, which is too large and wouldn't fit in the time frame.

EDIT 2: The next idea I had was to use Dijkstra's algorithm; simply make the end, the start, and the shortcuts all nodes in a graph. However, this becomes an O(N^2) solution (there are at most 10^10 edges!)

EDIT 3: I came up with another O(N^2) solution. Basically you would sort all the shortcuts based on their distance from their origin. Then, you would find the shortest path to each shortcut, by iterating through all the shortcuts you processed already. You would find the minimum of (distTo(each shortcut) + manhattan\_distance(each\_shortcut, current shortcut)). At the end, you would process the (N, N) point as if it was a shortcut to find your final solution.

However, this is still too slow - is there a way to optimize my solution further or a better one?