<p>Given a <code>m x n</code> <code>grid</code> filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.</p>

<p><strong>Note:</strong> You can only move either down or right at any point in time.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/05/minpath.jpg" style="width: 242px; height: 242px;" />
<pre>
<strong>Input:</strong> grid = [[1,3,1],[1,5,1],[4,2,1]]
<strong>Output:</strong> 7
<strong>Explanation:</strong> Because the path 1 &rarr; 3 &rarr; 1 &rarr; 1 &rarr; 1 minimizes the sum.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [[1,2,3],[4,5,6]]
<strong>Output:</strong> 12
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 200</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= 200</code></li>
</ul>

import heapq
import sys

REMOVED = (-1, -1)

class PriorityQueue:
    def __init__(self):
        self._h = []
        self._values = {}

    def push(self, e, priority):
        record = [priority, e]
        if e in self._values:
            if e[0] < priority:
                return
            self._values[e][-1] = REMOVED
        # print("push", record, "to", self._h)
        heapq.heappush(self._h, record)
        # print("push_result", self._h)
        self._values[e] = record

    def pop(self):
        if self.empty():
            return None, None
        record = heapq.heappop(self._h)
        # print("popping from", self._h)
        if record[-1] is REMOVED:
            # print("popped removed", record, ", left", self._h)
            return self.pop()
        del self._values[record[-1]]
        # print("popped", record, ", left", self._h)
        return record

    def empty(self):
        return len(self._h) == 0

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        # for row in grid:
        #     print(row)
        # print("-----")
        target = (len(grid[0]) - 1, len(grid) - 1)
        max_counter = len(grid) + len(grid[0]) - 2

        path_lengths = [
            [float('inf') for col in row]
            for row in grid
        ]
        path_lengths[0][0] = grid[0][0]
        visited = set()
        fringe = PriorityQueue()
        fringe.push((0, 0), grid[0][0])
        while not fringe.empty():
            cost, point = fringe.pop()
            if point is None:
                break
            visited.add((point))
            # print(point, cost)
            for row, col in self.children(point, grid):
                if (row, col) in visited:
                    continue

                new_cost = cost + grid[row][col]
                if new_cost < path_lengths[row][col]:
                    path_lengths[row][col] = new_cost
                
                fringe.push((row, col), new_cost)

        return path_lengths[len(grid) - 1][len(grid[0]) - 1]

    
    def children(self, point, grid):
        row, col = point
        if row < len(grid) - 1:
            yield (row + 1, col)
        if col < len(grid[0]) - 1:
            yield (row, col + 1)
24400