[Tag: Easy] TEXTBOOK TOGGLY-DIJKSTRA
This is toggly-dijkstra, and a really good question.

For each node i, in the dist array maintain two values
-> dist[i][0] = min dist from src to node i such th
This is toggly-dijkstra, and a really good question.

- For each node i, in the dist array maintain two values
-> dist[i][0] = min dist from src to node i such that landed on i in the first move from its previous node
-> dist[i][1] = min dist from src to node i such that landed on i in the second move from its previous node

- In the minHeap also while doing dijkstra 
-> ele.Item1 -> min dist of currNode from src 
-> ele.Item2.Item1 -> 0 if we landed on currNode in the first move from its previous node, else 1 if we landed on currNode in the second move from it's previous node
-> ele.Item2.Item2 -> the #node


```csharp []

public class Solution {
    int r;
    int c;
    int[] dX = new int[]{0,0,+1,-1};
    int[] dY = new int[]{-1,+1,0,0};
    public int MinTimeToReach(int[][] mat) {
        r = mat.Length;
        c = mat[0].Length;

        // ( dist from src, (0/1 where 0 is first move, 1 is second move, node) )
        SortedSet<(long, (int, int))> minHeap = new SortedSet<(long, (int, int))>(
            Comparer<(long, (int,int))>.Create((a, b) =>
            {
                int cmp1 = a.Item1.CompareTo(b.Item1);
                return cmp1 != 0 ? cmp1 : a.Item2.CompareTo(b.Item2);
            })
        );

        /*
        dist[i][0] -> minDist from src to node i such that reached i on first move
        dist[i][1] -> minDist from src to node i such that reached i on second move
        */
        long[][] dist = new long[r*c][];
        for (int i = 0; i < r*c; i++) dist[i] = new long[]{long.MaxValue, long.MaxValue};

        dist[0][0] = 0;
        dist[0][1] = 0;

        minHeap.Add((0,(0,0)));

        while(minHeap.Count > 0){
            var p = minHeap.Min();
            minHeap.Remove(p);

            int currNode = p.Item2.Item2;
            int moveBit = p.Item2.Item1;
            long currDist = p.Item1;

            if (currDist > dist[currNode][moveBit]) continue;

            int i = currNode / c;
            int j = currNode - i * c;

            for (int dir = 0; dir < 4; dir++){
                int adjI = i + dX[dir];
                int adjJ = j + dY[dir];

                if (!inBounds(adjI, adjJ)) continue;

                int adjNode = getNode(adjI, adjJ);

                long weight = 1 + (moveBit * 1) + Math.Max(0, mat[adjI][adjJ]-currDist);

                if (currDist + weight >= dist[adjNode][1-moveBit]) continue;

                dist[adjNode][1-moveBit] = currDist + weight;
                minHeap.Add((dist[adjNode][1-moveBit], (1-moveBit, adjNode)));
            }
        }

        return (int)dist[r*c-1].Min();
    }

    int getNode(int i, int j){
        return i * c + j;
    }

    bool inBounds(int i, int j){
        return i >= 0 && i < r && j >= 0 && j < c;
    }
}
```
['C#']