kittyK's blog

By kittyK, history, 6 weeks ago, In English

Anyone please help me with this problem

Here, you are asked to find second shortest path.

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

»
6 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

what complexity you need? what limit for n,m?

»
6 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Find shortest path from s to t using Dijkstra's algo. but, you should also store the value of the second best distance. So before overwriting smallestDistance, also store its discarded value. Do this only when the node in consideration is the target node. At the end, you would have second shortest distance.

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

now try this problem:P https://cses.fi/problemset/task/1196 the idea for the 2 case, as Ebiarat is just maintaining for information, here the distance of the second best path from s to t