Glad that you liked it. And yeah we do need visited array because when we are going to our neighboring elements it can happen that we come across same element as neighbor with some other element.
@@codetips-byRochak see this once Bhaiya , I don't use vis , and it works i think it will work bcz until we are not finding the less value of dist array then we will not update pq , and if we are not updating pq then it will empty when all element are visited.. pls conform this 🙏🙏... class Solution{ public: int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; int minimumCostPath(vector& grid){ int n=grid.size(); priority_queuepq; vectordist(n,vector(n,1e9)); dist[0][0]=grid[0][0]; pq.push({grid[0][0],{0,0}}); while(!pq.empty()){ int cost=pq.top().first; int xCo=pq.top().second.first; int yCo=pq.top().second.second; pq.pop(); for(int i=0;i=0&&newX=0&&newYgrid[newX][newY]+cost){ dist[newX][newY]=grid[newX][newY]+cost; pq.push({dist[newX][newY],{newX,newY}}); } } } } return dist[n-1][n-1]; } };
Yes bro it does work, but what I mean to say is it's safer to use visited array (although it does not require in this question), just as a template to solve these kind of question. It doesn't require in this question but it might require in some other variation for these kind of problems.
Dp will increase the complexity by reaching out to each and every state( because just imagine, if we are at cell x,y and we go to top, and again through some other path we again come across x,y with some lower path sum, so we are going to same node again and again, so here we are not restricted with one forward direction, we are also considering backward direction, so it can keep on going to find minimum sum, by going forward direction, backward direction,forward direction again, and so on....), but Dijkstra will stop when we encounter bottom right cell, because that will be minimum sum because we are keeping min heap. Hope you understood.
Let's Connect 🤝 :
LinkedIn : www.linkedin.com/in/rochak-vyas17/
TY :)
Glad you liked it
Great Explanation Bhaiya , Love You 🧡🧡🧡🧡
Bhaiya i think there will be no need of visited vector as we are using priority_queue ...
Glad that you liked it.
And yeah we do need visited array because when we are going to our neighboring elements it can happen that we come across same element as neighbor with some other element.
@@codetips-byRochak see this once Bhaiya , I don't use vis , and it works i think it will work bcz until we are not finding the less value of dist array then we will not update pq , and if we are not updating pq then it will empty when all element are visited..
pls conform this 🙏🙏...
class Solution{
public:
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int minimumCostPath(vector& grid){
int n=grid.size();
priority_queuepq;
vectordist(n,vector(n,1e9));
dist[0][0]=grid[0][0];
pq.push({grid[0][0],{0,0}});
while(!pq.empty()){
int cost=pq.top().first;
int xCo=pq.top().second.first;
int yCo=pq.top().second.second;
pq.pop();
for(int i=0;i=0&&newX=0&&newYgrid[newX][newY]+cost){
dist[newX][newY]=grid[newX][newY]+cost;
pq.push({dist[newX][newY],{newX,newY}});
}
}
}
}
return dist[n-1][n-1];
}
};
Yes bro it does work, but what I mean to say is it's safer to use visited array (although it does not require in this question), just as a template to solve these kind of question. It doesn't require in this question but it might require in some other variation for these kind of problems.
@@codetips-byRochak got it 🧡🧡🧡🧡☺☺☺☺
@@codetips-byRochak ook Got It
why not DP?
Dp will increase the complexity by reaching out to each and every state( because just imagine, if we are at cell x,y and we go to top, and again through some other path we again come across x,y with some lower path sum, so we are going to same node again and again, so here we are not restricted with one forward direction, we are also considering backward direction, so it can keep on going to find minimum sum, by going forward direction, backward direction,forward direction again, and so on....), but Dijkstra will stop when we encounter bottom right cell, because that will be minimum sum because we are keeping min heap.
Hope you understood.