Wrong Answer in Chef and Reversing

general
1

Here is the question-> REVERSE Problem - CodeChef

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-> CodeChef: Practical coding for everyone

Plzz Help…

2

@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:

	if(visited[n-1])
	{
	    cout<<dist[n-1]<<endl;
	}
	else
	{
	    cout<<"-1\n";
	}

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: CodeChef: Practical coding for everyone)