###########################################################################
#                                                                         #
# Author: Daniel Mock                                                     #
#                                                                         #
# Purpose: To document progress in learning algorithms & data structures  #
#                                                                         #
# References: This question was generated by leetcode.com. The solution   #
# to the question was generated by Daniel Mock.                           #
#                                                                         #
###########################################################################


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        heap = [(grid[0][0], 0,0)]
        cost = [[float('inf') for i in range(len(grid[0]))] for j in range(len(grid))]
        while heap:
            weight, i,j = heapq.heappop(heap)
            if (i,j) == (len(grid)-1, len(grid[0])-1):
                return weight
            for x, y in (1,0), (0,1):
                if i+x < len(grid) and j+y < len(grid[0]):
                    if cost[i+x][j+y] > weight + grid[i+x][j+y]:
                        cost[i+x][j+y] = weight + grid[i+x][j+y]
                        heapq.heappush(heap,(weight+grid[i+x][j+y], i+x, j+y))
