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

TreeSet much faster than PriorityQueue — Dijkstra
Автор Armyx, история, 9 лет назад, По-английски

I solved this problem http://codeforces.me/contest/449/problem/B using dijkstra based on priority queue and I got TLE (http://codeforces.me/contest/449/submission/13186398) on test 45. After that I changed it to TreeSet ( http://codeforces.me/contest/449/submission/13186483 ) and it runs ~940ms instead of > 2000ms . What is wrong with my previous solution ? I read that priority queue runs faster in practice and I saw that most java solutions use priority queue

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

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

Priority queue doesn't work in Dijkstra when you store only indices in it, try to think why.

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

    Priority queue doesn't work in Dijkstra when you store only indices in it

    it does: 13187441

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

      When the distance to some vertex is changed, this vertex doesn't change its position in the priority queue, while it should to maintain the heap property value(parent) <= value(child). So it's just weak tests.

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        CountZero has defined a custom comparison for the PriorityQueue and ignores vertices already visited so it is fundamentally correct.

        EDIT: Have a look at the analysis

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

          lol, no. Now I see dalex is right. Take a closer look at my code — there are no guarantees for heap property to be maintained. Anyway, we can implement Dijkstra algorithm using priority queue and custom comparator — we need a custom priority queue with method "delete any element".

          → Ответить
          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
            ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            Understood my mistake. Please ignore.

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

            BTW, you don't need 'delete any element' in priority-queue.

            You can store a pair <vertex,distance(vertex)> in the priority-queue.

            → Ответить