Блог пользователя kittyK

Автор kittyK, история, 4 года назад, По-английски

Anyone please help me with this problem

Here, you are asked to find second shortest path.

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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