Advertisement
spider68

Minimum Cost Path

Jun 27th, 2021
974
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None | 0 0
  1. typedef pair<int, int> ipair;
  2. int dx[]={0,0,-1,1};
  3. int dy[]={1,-1,0,0};
  4. class Solution
  5. {
  6.     public:
  7.     int minimumCostPath(vector<vector<int>>& grid)
  8.     {
  9.         int m=grid.size(),n=grid[0].size();
  10.         priority_queue< pair<int,ipair>,vector<pair<int,ipair>>, greater<pair<int,ipair>> >pq;
  11.         vector<vector<int>>dis(m,vector<int>(n,INT_MAX));
  12.        
  13.         dis[0][0]=grid[0][0];
  14.         pq.push({dis[0][0],{0,0}});
  15.         while(!pq.empty()){
  16.             auto p=pq.top();
  17.             pq.pop();
  18.             int dist=p.first,x=p.second.first,y=p.second.second;
  19.             for(int i=0;i<4;i++){
  20.                 int cx=x+dx[i],cy=y+dy[i];
  21.                 if(cx<0 ||cx>=m ||cy<0 ||cy>=n)continue;
  22.                 if(dis[cx][cy]>dis[x][y]+grid[cx][cy]){
  23.                     dis[cx][cy]=dis[x][y]+grid[cx][cy];
  24.                     pq.push({dis[cx][cy],{cx,cy}});
  25.                 }
  26.             }
  27.         }
  28.         return dis[m-1][n-1];
  29.     }
  30. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement