priority_queue<ar<ll, 2>, vector<ar<ll, 2>>, greater<ar<ll, 2>>> pq;
pq.push({0, 0});
memset(d, 0x3f, sizeof(d));
d[0] = 0;
while (pq.size()) {
ar<ll, 2> u = pq.top();
pq.pop();
if ( u [0] > d[ u[1] ] ) // i have a doubt here
continue;
for (ar<ll, 2> v : adj[u[1]]) {
if (d[v[1]] > u[0] + v[0]) {
d[v[1]] = u[0] + v[0];
pq.push({d[v[1]], v[1]});
}
}
}
I do not understand why if ( u [0] > d[ u[1] ] ) continue; in the code .please give the reason ,is it related to connected component?
You cannot efficiently erase an element from the priority queue.
Let's start from node 1. Suppose you start from node 1, and there 1->2, 2->3, 1->3 edges.
Then at the first iteration 2, 3 are pushed into the queue, but at the second iteration (node 2), if 1->2 + 2->3 is better than 1->3, 3 would be pushed into the queue again. The continue part takes care of situations like this. Since if u[0]>d[u[1]] then you would have processed pq.top() = {d[u[1]], u[1]} before, you simply don't need the iteration for this same vertex again so just continue.