Getting WA in Easy Dijkstra problem

general
,
1

I am getting WA in the question but my code is giving correct answer on the test-cases given and even on the spoj toolkit 
https://ideone.com/uro6bE
2

You’re trying to identify vertices that are not connecting by setting their distance to a huge value, that cannot by reached by a distance of two connected vertices. In principle that’s fine. But the “huge” value with which you’re initializing the distances is 0x3F, which is clearly not big enough.

Try to bound the maximal distance two connected vertices can have (using the constraints of the problem) and set the initial value of the distances to a bigger value. Then check for that value when you’re determining whether two vertices are connected.

3

@artist
Apart from what @ceilks has pointed out, your code also has a logical problem. In your Dijkstra function you are pushing elements on the priority queue from the adjacency list itself (thereby using original weight as specified in original graph) , while you should do so with the changed cost.
You can view the corrected code http://ideone.com/xZhuTP (AC).
Corrections :

  • Line 58-59 : Pushing in correct pair
  • Using infinity = 100000005

P.S: I have an accepted solution using int only, long long is not really required.