Invitation to CodeChef January Lunchtime 2020

[rahulb1999]

you have used a max heap in your c++ code which is wrong. python on the other hand has a minheap by default.

[l_returns]

@anon31329220

if you would have googled out during the contet time
solution on stack overflow

@kharyusuf

[kshitij_789]

thanks totally forgot

[infinitepro]

Exactly! Nice catch.
@kshitij_789 You confused yourself with Dijkstra and DFS. You used a visited bool array like in DFS and used a heap (max heap) like in Dijkstra. This caused the problem, as once a vertex was relaxed, it wasn’t being relaxed again (even when a shorter path existed), leading to incorrect answers.

[kshitij_789]

@kshitij_789 You confused yourself with Dijkstra and DFS. You used a visited bool array like in DFS and used a heap (max heap) like in Dijkstra. This caused the problem, as once a vertex was relaxed, it wasn’t being relaxed again (even when a shorter path existed), leading to incorrect answers.

I remove that in contest see I had around 10 submissions.maybe you didn’t check the other ones.

problem was I used max_heap and used it like a min heap…
lesson learnt-do not overcomplicate bfs to djikstra