What does this do?

general
1

http://usaco.org/current/data/sol_visitfj_gold_feb17.html

So I was reading this analysis, and when I understand most of it, I couldn’t figure out the purpose of this piece of code:

int d = -q.top().first;
.
.
q.push(make_pair(-D[nr][nc], nr * N + nc));

What is the purpose of the double negative? On removing the negatives, the code results in a TLE on some of the test-cases.

~Thanks

2

We used -(negative) sign in the insertion of queue only if we are required to make the priority queue as min heap. Since by default insertion in priority queue will be happened as MAX heap.

Therefore we are using -(negative) sign two times to nullify the effect of actual or absolute value with an advantage of MIN heap.

If you still have any doubt then feel free to ask again.

1 Like
3

Ah right, thanks!
I should have realized that myself. >_>