when you pop the queue don’t explore that node if it’s current distance is less than the popped distance from the queue.
As a side note, these lines inside main are useless:
lli dist[v+1]={0};
bool flags[v+1]={0};
when you pop the queue don’t explore that node if it’s current distance is less than the popped distance from the queue.
As a side note, these lines inside main are useless:
lli dist[v+1]={0};
bool flags[v+1]={0};
I don’t understand what i should change ? can u please edit my code .
while(!pq.empty()){
pii mpair = pq.top();
lli u = mpair.S;
pq.pop();
for(auto xt : adj[u]){
lli v = xt.F;
lli weight = xt.S;
if(dist[v] > (dist[u] + weight) )
{
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v] , v));
}
}
}
Just one line added…
while(!pq.empty()){
pii mpair = pq.top();
lli u = mpair.S;
pq.pop();
if (mpair.first > dist[u]) continue;
for(auto xt : adj[u]){
lli v = xt.F;
lli weight = xt.S;
if(dist[v] > (dist[u] + weight) )
{
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v] , v));
}
}
}
Yeah before u answer i changed and AC…thanks
Can u please give me an simple example where I unnecessarily explore the nodes , bcz I don’t understand how a single if made program AC , Please give an example so I can understand more better.
build yourself a complete graph (every node connected with every node) with random weights and do it on paper
Thanks , Now I understand , same pair of node with the different cost is added in min heap so when higher cost pair is poped then there is no meaning for that node as already by smaller cost we explored its adjacent, Thanks man .
Surprised to see every other Dijkstra implementation online misses this. .
yes and it increases complexity too much , one of problem on leet code passes with 300 ms but when I put if condition ( as caree said) , then it passed in 200 ms only.
As said here, “…this check is important, otherwise the complexity can increase up to O(nm)”.
A bit late, but I always liked this one:
Will try , btw u come after very long time…
It’s never too late! . Keep `em coming.
yeah lol