Wrong Answer in Chef and Reversing

Here is the question-> https://www.codechef.com/problems/REVERSE

I have implemented the algo described in the editorial which is basically dijkstra’s algorithm but don’t know why i am getting WA.

here is my solution-> https://www.codechef.com/viewsolution/18741652

Plzz Help…

@swapnil159 The problem is with your implementation of Dijkstra’s algorithm.

More than my words I think this test case will tell you where the problem is:

7 6
3 2
3 4
7 4
6 2
5 6
7 5

Expected output: -1

Your this condition:


First if will be true for all cases(not sure for all but for most cases because in your implementation you’ve used for which kinda scares me). This is because you push all the nodes in the set s.insert(mp(dist[a],a));.

I think by now you may have understood where the problem is, but I can explain it more if still, it isn’t clear.

(Here is my submission: https://www.codechef.com/viewsolution/18753287)