harshhks's blog

By harshhks, history, 4 years ago, In English

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?

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I think you have integer overflow in your Dijkstra. You assigned d_v as int.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That solved my problem. Thanks for your help!