Dijkstra's algorithm question

Question

In the code below:

#define MAX_VERTICES 260000

#include <fstream>
#include <vector>
#include <queue>
#define endl '\n'
using namespace std;

struct edge {
    int dest;
    int length;
};

bool operator< (edge e1, edge e2) {
    return e1.length > e2.length;
}

int C, P, P0, P1, P2;
vector<edge> edges[MAX_VERTICES];
int best1[MAX_VERTICES];
int best2[MAX_VERTICES];

void dijkstra (int start, int* best) {
    for (int i = 0; i < P; i++) best[i] = -1;
    best[start] = 0;
    priority_queue<edge> pq;
    edge first = { start, 0 };
    pq.push(first);
    while (!pq.empty()) {
        edge next = pq.top();
        pq.pop();
        if (next.length != best[next.dest]) continue;
        for (vector<edge>::iterator i = edges[next.dest].begin(); i != edges[next.dest].end(); i++) {
            if (best[i->dest] == -1 || next.length + i->length < best[i->dest]) {
                best[i->dest] = next.length + i->length;
                edge e = { i->dest, next.length+i->length };
                pq.push(e);
            }
        }
    }
}

int main () {
    ifstream inp("apple.in");
    ofstream outp("apple.out");

    inp >> C >> P >> P0 >> P1 >> P2;
    P0--, P1--, P2--;
    for (int i = 0; i < C; i++) {
        int a, b;
        int l;
        inp >> a >> b >> l;
        a--, b--;
        edge e = { b, l };
        edges[a].push_back(e);
        e.dest = a;
        edges[b].push_back(e);
    }

    dijkstra (P1, best1);           // find shortest distances from P1 to other nodes
    dijkstra (P2, best2);           // find shortest distances from P2 to other nodes

    int ans = best1[P0]+best1[P2];  // path: PB->...->PA1->...->PA2
    if (best2[P0]+best2[P1] < ans) 
        ans = best2[P0]+best2[P1];  // path: PB->...->PA2->...->PA1
    outp << ans << endl;
    return 0;
}

What is this: if (next.length != best[next.dest]) continue; used for? Is it to avoid us situations where going through the loop will give us the same answer that we already have?

Thanks!

Answer 1

That line is a way to handle the fact that c++'s priority_queue does not have a decrease_key function.

That is, when you do pq.push(e) and there is already an edge with the same destination in the heap you would prefer to decrease the key of the edge already in the heap. This is not easily done with c++'s priority_queue and so a simple way to handle it is to allow multiple edges in the heap corresponding to the same destination and ignoring all but the first (for each dest) that you pop from the heap.

Note that this changes the complexity from O(ElogV) to O(ElogE).