LunaticPriest's blog

Finding the shortest path with a small twist
By LunaticPriest, history, 5 years ago, In English

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!

  • Vote: I like it
  • +35
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply