CSES problem set Dijkstra doubt

Revision en1, by harshhks, 2021-03-02 10:34:33

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?

Tags #cses, #dijkstra

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English harshhks 2021-03-02 10:34:33 785 Initial revision (published)