Python | C++ Dijkstra
\n\n# Complexity\n- Time complexity: O(ElogE)\n\n- Space complexity: O(ElogE)\n\n# Code\npython []\nclass Solution:\n    def minTimeToReach(self, moveTime: List
\n\n# Complexity\n- Time complexity: O(ElogE)\n\n- Space complexity: O(ElogE)\n\n# Code\n```python []\nclass Solution:\n    def minTimeToReach(self, moveTime: List[List[int]]) -> int:\n        m, n = len(moveTime), len(moveTime[0])\n        pq: list[tuple[int]] = [(0, 0, 0, 0)]\n        min_time: list[list[int]] = [[float(\'inf\')] * n for _ in range(m)]\n        min_time[0][0] = 0\n        directions: list[tuple[int]] = [(1, 0), (-1, 0), (0, 1), (0, -1)]\n        while pq:\n            curr_time, r, c, is_extra = heapq.heappop(pq)\n            if r == m - 1 and c == n - 1:\n                return max(curr_time, moveTime[r][c])\n\n            if curr_time > min_time[r][c]:\n                continue\n            \n            for dr, dc in directions:\n                nr, nc = r + dr, c + dc\n                if 0 <= nr < m and 0 <= nc < n:\n                    next_time = max(curr_time, moveTime[nr][nc]) + [1, 2][is_extra]\n                    if next_time < min_time[nr][nc]:\n                        min_time[nr][nc] = next_time\n                        heapq.heappush(pq, (next_time, nr, nc, ~is_extra))\n        return -1\n```\n```cpp []\nclass Solution {\npublic:\n    int minTimeToReach(vector<vector<int>>& moveTime) {\n        int m = moveTime.size();\n        int n = moveTime[0].size();\n        std::priority_queue<std::vector<int>, std::vector<std::vector<int>>, std::greater<std::vector<int>>> pq;\n        pq.push({0, 0, 0, 0});\n        std::vector<std::vector<int>> minTime(m, std::vector<int>(n, 1100000000));\n        std::vector<std::pair<int, int>> directions = {\n            {0, 1}, {0, -1}, {1, 0}, {-1, 0}\n        };\n        while (pq.size()) {\n            int currentTime = pq.top()[0];\n            int currentRow = pq.top()[1];\n            int currentCol = pq.top()[2];\n            bool isExtra = pq.top()[3];\n            pq.pop();\n            if (currentRow == m - 1 && currentCol == n - 1) {\n                return std::max(currentTime, moveTime[m - 1][n - 1]);\n            }\n            if (currentTime >= minTime[currentRow][currentCol]) {\n                continue;\n            }\n            minTime[currentRow][currentCol] = currentTime;\n            for (std::pair<int, int> direction : directions) {\n                int nextRow = currentRow + direction.first;\n                int nextCol = currentCol + direction.second;\n                \n                if (0 <= std::min(nextRow, nextCol) && nextRow < m && nextCol < n) {\n                    int nextTime = std::max(currentTime, moveTime[nextRow][nextCol]) + (isExtra? 2 : 1);\n                    pq.push({nextTime, nextRow, nextCol, !isExtra});\n                }\n            }\n        }\n        return -1;\n    }\n};\n```
['Array', 'Graph', 'Heap (Priority Queue)', 'Matrix', 'Shortest Path', 'C++', 'Python3']