Anyone please help me with this problem
Here, you are asked to find second shortest path.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 166 |
2 | maomao90 | 163 |
2 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | adamant | 160 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | nor | 153 |
9 | Dominater069 | 153 |
Название |
---|
what complexity you need? what limit for n,m?
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.
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