bool compare_heap_elements(PNode n1, PNode n2)
{
    // Compares 2 heap elements, and if they are to be swaped,
    // it also changes their heap indexes
    if (GREATER(n1->dist_time, n2->dist_time)) {
        XCHG(n1->heap_index, n2->heap_index);
        return true;
    }
    if(EQUAL(n1->dist_time, n2->dist_time) &&\
       n1->max_fuel > n2->max_fuel) {
        XCHG(n1->heap_index, n2->heap_index);
        return true;
    }
    return false;
}

PPath getBestPathByMax(UINT16 max)
{
    // Dijkstra using a heap as Queue
    vector<PNode> Q;

    // Due to the need of saving each element heap index, after poping from the heap,
    // each index in the heap will be delayed by one. We keep in heap_delay the number
    // of pop() operations on the heap.
    UINT16 heap_delay = 0;

    // We initialize the nodes and the heap.
    nodes[s_node]->parent = NULL;
    nodes[s_node]->visited = true;
    for (UINT16 i = 0; i < nodes.size(); i ++)
        if(i != s_node)
            nodes[i]->visited = false;
    for (UINT16 i = 0; i < nodes[s_node]->neigh.size(); i ++) {
        UINT16 neigh_index = nodes[s_node]->neigh[i]->index;
        nodes[s_node]->neigh[i]->dist_time = log10(t[s_node][neigh_index]);
        nodes[s_node]->neigh[i]->heap_index = i;
        nodes[s_node]->neigh[i]->in_heap = true;
        nodes[s_node]->neigh[i]->max_fuel =\
        nodes[s_node]->neigh[i]->temp_fuel = c[s_node][neigh_index];
        if(nodes[s_node]->neigh[i]->is_key)
            nodes[s_node]->neigh[i]->temp_fuel = 0;
        nodes[s_node]->neigh[i]->parent = nodes[s_node];
        HEAP_INSERT(Q, nodes[s_node]->neigh[i]);
    }

    int i = 0;
    while (Q.size()) {
        // We get the next node in the heap. If it's the destination node
        // we break out of the while loop.
        PNode crt_node = Q[0];
        pop_heap(Q.begin(), Q.end(), compare_heap_elements);
        Q.pop_back();
        if(d_node == Q[0]->index)
            break;
        heap_delay ++;
        crt_node->visited = true;

        // We check all his neighbours.
        for (UINT16 i = 0; i < crt_node->neigh.size(); i ++) {
            PNode neigh_node = crt_node->neigh[i];
            // The total time to get from the source node to the neigh_node
            // passing trough crt_node.
            double added_dist_time = crt_node->dist_time +\
                                     log10(t[crt_node->index][neigh_node->index]);
            // The total fuel needed to get from the source node to the neigh_node
            // passing trough crt_node.
            UINT16 added_fuel = crt_node->temp_fuel +\
                                c[crt_node->index][neigh_node->index];

            if (\
                // The best time cost wasn't already decided for this node.
                !neigh_node->visited &&\
                // The time is better than any precalculated one.
                GREATER(neigh_node->dist_time, added_dist_time) &&\
                // The fuel cost shouldn't get bigger than the max capacity of
                // our ships.
                added_fuel <= max
                )
            {
                // We update the node.
                neigh_node->parent = crt_node;
                neigh_node->dist_time = added_dist_time;
                neigh_node->max_fuel = MAX(crt_node->max_fuel , added_fuel);

                // We recalculate the built-up fuel cost from the last key or
                // source planet considering the case the current planet is a key one.
                if(neigh_node->is_key)
                    neigh_node->temp_fuel = 0;
                else
                    neigh_node->temp_fuel = added_fuel;
                // We update our heap.
                if(neigh_node->in_heap)
                    push_heap(Q.begin(), Q.begin() + neigh_node->heap_index - heap_delay,\
                              compare_heap_elements);
                else {
                    HEAP_INSERT(Q, neigh_node);
                    neigh_node->heap_index = Q.size() + heap_delay;
                    neigh_node->in_heap = true;
                }
            }
        }
    }

    PPath best_path = new Path;
    PNode crt_node = nodes[d_node];
    while (crt_node != NULL) {
        best_path->push_back(crt_node);
        crt_node = crt_node->parent;
    }

    return best_path;
}