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

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

Anyone please help me with this problem

Here, you are asked to find second shortest path.

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

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

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

»
6 лет назад, скрыть # |
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.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +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