min_path_sum.cpp

class Solution {
public:
  
    struct Position{
      int row;
      int col;
      int cost;
    };
  
    int toIndex(int M, int r, int c) {
      return (r*M) + c;
    }
  
    int pathCost(const vector<vector<int>>& grid, int rowFrom, int colFrom, int rowTo, int colTo) {
      return grid[rowTo][colTo];
    }
  
    int minPathSum(vector<vector<int>>& grid) {
      auto N = grid.size();
      auto M = grid[0].size();
      
      vector<int> dist(N*M, 1e9); //set to maximum in the beginning
      dist[0] = 0; //starting position is 0
      
      auto compare = [](const Position& lhs, const Position& rhs) {
        return lhs.cost > rhs.cost;
      };
      priority_queue<Position, vector<Position>, decltype(compare)> pq(compare);
      
      //visit starting position (getting to starting location is 0 cost, we will add the starting cost of 0,0 at the very end)
      pq.push({0, 0, 0});
      while (pq.size()) {
        auto [row, col, cost] = pq.top(); pq.pop();
        
        array<int, 3> offsets = {1,0,1};
        for (auto i = 0; i < offsets.size()-1; ++i) {
          auto newRow = row + offsets[i], newCol = col + offsets[i+1];
          
          //remove out of bounds neighbors if any
          if (newRow > N-1 || newCol > M-1) continue;
          
          auto potential = cost + pathCost(grid, row, col, newRow, newCol);
          auto newIndex = toIndex(M, newRow, newCol);
          if (potential < dist[newIndex]) {
            dist[newIndex] = potential;
            pq.push({newRow, newCol, potential});
          }
        }
      }
      
      auto startingCost = grid[0][0];
      return startingCost + dist[toIndex(M, N-1, M-1)];
    }
};