Hi, the mightly Codeforces community! I'm having some problems with an easy shortest path question. I'm trying to solve Jzzhu and Cities and my code gets a TLE at 45th test case :( I'm basically using Dijkstra's Algo, only with the optimization that I store the information whether a node is reached by a railroad or a normal one. Here is the code. Thanks in advance for all your optimization advice, I'll do my best!
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
15:28:22
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
15:28:22
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 02:06:40 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
Because in a priority queue based Dijkstra there is a twist itself.
You either need to pop the nodes directly from the priority queue (which is rarely used) or you do the lazy-deletion hack where you pop the top of the queue if it is no longer valid.
Check out the difference between 66995018 and 66995014.
The Dijkstra without the hack or the popping does not have the complexity of $$$O(E \cdot \log V)$$$
Thank you for the wonderful explanation and all the effort! Now I understood my mistake and will never repeat!!