Hey guys,I just encountered with a very Interesting and tough problem(at least for me).It is asked to calculate second shortest path from node 1 to N.Can anybody have some idea how to solve this with Dijktra's .In case you want to check if I have tried or not see this(yes,I know I have done nothing special but normal dijktras)
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 18.04.2026 09:30:47 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Hint: apply 2 dijkstras one from vertex No.1 and the other from vertex No.n and check every edge Maybe that works just maybe xD
You mean you are also not so sure.
This almost works for all the problems of dijkstra (sorry don't have time to corret my english)
Nobody asked to correct anything sir,you are awesome :).Thank you for suggesting me your approach.Really appreciate that :)
you're welcome btw other's solution works too but this is a nice approach
You mean check, for each edge, if the 2nd shortest path goes through that edge?
Yep that's what i meant
I don't understand what you are trying to do in details, but are you handling the case where every path is a shortest path?
The problem allows you to use an edge more than once...you can't out -1.
Let Dv, k be the kth shortest path to node v. Suppose we get to v from the 3rd shortest path to node u, then it means Dv, 2 = Du, 3 + [u, v], where [u, v] denotes the road from u to v. But Du, 1 < Du, 2 < Du, 3, so it means both Du, 1 + [u, v] and Du, 2 + [u, v] are less than Du, 3 + [u, v], which is a contradiction, since Dv, 2 would be at least the 3rd shortest path to v. So we don't need to keep track of more than 2 shortest paths for each node.
I coded a Dijkstra storing the two shortest paths for each node, and I believe it should be OK, but I don't have a way to try it out because I can't register at Light OJ.
Here's the code, just in case: C++ Code
UPDATE: Finally, the login data arrived at my e-mail and I was able to test the code. It got AC, so yes, it's the correct idea.
Don't know why but your solution gives me sense of some sort of DP+Graph problem.Correct me if I am wrong.I am trying what you explained with pen and paper in hope of getting better understanding.Btw can you tell me what is the level of this question.I mean like div2 B or so..
it's like one of the easiest dijkstra's it's actually div 2 D
It's actually a normal Dijkstra, but every node keeps 2 values instead of one. You have to be careful to only consider different distances.
Difficulty is clearly not Div2 B, but rather around Div 2D.
Implement Dijkstra, but instead of keeping just one array Dist, keep two of them — DistActual and DistSecond. Each time you find a shorter path to the node
I, move the value fromDistActual[i]toDistSecond[i], and place the new shortest path inside theDistActual[i].And since before start all the DistActual are equal to INFINITY, if there is no second shortest path, the DistSecond[i] will be equal to INF.
There's also the chance that you may need to update only DistSecond and DistActual stays the same.