### harshhks's blog

By harshhks, history, 7 weeks ago,

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

 » 7 weeks ago, # |   +5 I think you have integer overflow in your Dijkstra. You assigned d_v as int.