Dijkstra question in Google interview 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\u8FD9\u4E2A\u89E3\u6CD5\u5E76\u6CA1\u6709\u771F\u7684\u201C\u9000\u56DE\u53BB\u201D\uFF0C\u800C\u662F\u901A\u8FC7\u539F\u5730\u7B49\u5F85\u6765\u6EE1\u8DB3\u65F6\u95F4\u7EA6\u675F\u3002 \n# Approach\n<!-- Describe your approach to solving the problem. -->\n\u4E3A\u4EC0\u4E48\u4E0D\u9700\u8981\u56DE\u9000\n1. \u52A8\u6001\u89C4\u5212\u601D\u8DEF\uFF1A\n\n\u6BCF\u6B21\u90FD\u4ECE\u5806\u4E2D\u53D6\u51FA\u5F53\u524D\u65F6\u95F4\u6700\u77ED\u7684\u8DEF\u5F84\uFF0C\u8FD9\u79CD\u8D2A\u5FC3\u7B56\u7565\u4FDD\u8BC1\u4E86\u8DEF\u5F84\u7684\u6700\u4F18\u6027\u3002\n\u539F\u5730\u7B49\u5F85\u5DF2\u7ECF\u53EF\u4EE5\u8C03\u6574\u65F6\u95F4\u5230\u7B26\u5408\u8981\u6C42\u7684\u72B6\u6001\uFF0C\u65E0\u9700\u591A\u4F59\u7684\u56DE\u9000\u64CD\u4F5C\u3002\n2. \u6027\u80FD\u4F18\u5316\uFF1A\n\n\u5982\u679C\u5B9E\u73B0\u56DE\u9000\uFF0C\u4F1A\u5F15\u5165\u989D\u5916\u7684\u8DEF\u5F84\u8BB0\u5F55\u548C\u590D\u6742\u7684\u903B\u8F91\u5224\u65AD\uFF0C\u589E\u52A0\u7B97\u6CD5\u590D\u6742\u5EA6\u548C\u8FD0\u884C\u65F6\u95F4\u3002\n\u539F\u5730\u7B49\u5F85\u7684\u5B9E\u73B0\u66F4\u76F4\u63A5\uFF0C\u4E5F\u7B26\u5408\u5B9E\u9645\u95EE\u9898\u7684\u9700\u6C42\u3002\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO((m\xD7n)\u22C5log(m\xD7n))\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(m\xD7n)\n# Code\n```python3 []\nimport heapq \nclass Solution:\n    def minimumTime(self, grid: List[List[int]]) -> int:\n        if not grid:\n            return -1\n        if grid[0][1] > 1 and grid[1][0] > 1:\n            return -1\n        ROWS, COLS = len(grid), len(grid[0])\n        directions = [(-1,0), (1,0), (0,1), (0,-1)]\n        minHeap = [(0, 0, 0)] # current_time, row, col  \n        visited = set()\n        visited.add((0,0)) # row and col \n        while minHeap:\n            current_time, row, col = heapq.heappop(minHeap)\n            if row == ROWS - 1 and col == COLS - 1:\n                return current_time \n            for dr, dc in directions:\n                nr, nc = dr + row, dc + col   \n                if 0 <= nr < ROWS and 0 <= nc < COLS and (nr, nc) not in visited:\n                    # \u904D\u5386\u56DB\u4E2A\u65B9\u5411 (dr, dc), \u8BA1\u7B97\u90BB\u5C45\u5355\u5143\u683C (nr, nc) \n                    waitTime = max(0, grid[nr][nc] - (current_time + 1)) \n                    if waitTime % 2 == 1:\n                        waitTime += 1\n                    new_time = waitTime + current_time + 1\n                    visited.add((nr,nc)) \n                    heapq.heappush(minHeap, (new_time, nr, nc)) \n        return -1\n\n\n\n```
['Python3']