I am attempting this question, and I am getting a couple of wrong answer for big test cases but every thing seems to work fine for small test cases.
Here's my approach...
-Firstly find shortest path from 1 to every node. (answers in array d1)
-Then find shortest path from N to every node (on Inverted graph) which means finding shortest path from every node to N.(answers in array d2)
-Then consider each edge in graph , suppose you are applying discount on that edge... then if we can reach 1 to a and N to b (in short b to N) then ans = min( ans , d1[a] + d2[b] + edge.weight/2 )
Here is my code
Can someone please help me with it? What am I doing wrong?