I got an AC with dynamic programming and without a graph and I am frustrated with my memory consumption. I used C++ for this and i've got 0,31s and 16000 KB. I guess my solution consumed so much memory because I've stored 2 matrices, one for grid second for diagonales.

Matrix[i][j] = min (Matrix[i-1][j]+100, Matrix[i][j-1]+100, Matrix[i-1][j-1] + Diag[i][j])
where Diag[i][j] is either 100 * sqrt(2) or Infinity.
I wonder if there is a better solution. I think a simple BFS could give me an answer, Bellman-Ford and Dijkstra's algorithms will give it for sure though. Nevertheless, I've never worked with a graph where every vertex is a 2D point. How should i store it? vector <int> g[maxN][maxN] ? How do I fill it with values efficently?

But when Diag[i][j] get infinity sir

I think the main cause of memory consumption is the matrix of DOUBLES. Even a simple array of doubles consumes a lot of memory.
Even for the solution involving graph and shortest paths would use 'huge' amount of memory, since you would also need a 2 dimensional array of doubles (I suppose).
I managed to solve it using 9360KB.

Edited by author 14.06.2018 17:45

a better solution is to use dynamic programming to find the longest increasing sequence of diagonals, which there are 100 at most.
then
```
min = (n + m - maxDiagonals * 2) * distance + maxDiagonals * diagonalDistance
```