Hello Codeforces!
I've seen people using negative edges when creating a priority queue because writing a minimum is simply too tedious. And, I gotta say, I agree with them! Look at this code when you have to declare a min heap for a pair of ints:
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
That simply is too much to write! However, there is a simple solution. Just include this somewhere near the top of your code:
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
Now you can declare a min heap of pairs of ints by writing:
min_heap<pair<int, int>> q;
To me, that is more clear and concise, and less to type! Are there any other reasons that some people might create a min heap by negating edge weights instead of writing that block of code at the top?
When I perform dijkstra.I always use prioroty_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int> > > pq;
How does that work?! Dikstra requires you to modify elements which are not at the top of the heap. And pq doesn't allow that. How can you use pq for dikstra?! I have always used set.
Instead of modifying element inside PQ, just push the new pair. But when popping element from PQ, check if the distance matches the currently known distance. If it doesn't, then just ignore that pair.
Oh, that's slightly inefficient than set I guess. Overall , we are storing more elements, right?
The complexity is the same for both. But
priority_queuegives better runtime thansetactually.Just use priority_queue and use negative values for min heap.
I do this, this method allows other comparisons rather than only min / max. For example, if you want to prioritize the pair of ints with smaller sum,
and pq always spits out the pair that has the smallest sum.