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

Finding the shortest path with a small twist
Автор LunaticPriest, история, 4 года назад, По-английски

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!

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

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

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)$$$

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Thank you for the wonderful explanation and all the effort! Now I understood my mistake and will never repeat!!

    → Ответить