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

[SOLVED] Why getting TLE in dijkstra straight forward implementation ?
Автор nipul1, история, 5 лет назад, По-английски

I am trying problem Problem using dijkstra algorithm. my submission is submission please tell me where I'm wrong in this .

Thanks in Advanced.

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

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

From the documentation, you can see that priority queues are max heaps, meaning that they will pull out the largest element first. Dijkstra's is a greedy algorithm that runs fast if you relax the nearest (smallest distance) vertex first.

You can fix this by changing the '<' in your comparator to '>'. After that, you will get MLE on test 31.

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

You need to avoid using pair<int, int> and use your own struct. Here is your code, but I've replaced the pair<int, int> with struct arista: https://mirror.codeforces.com/contest/20/submission/57781763

Also note I've declared the 'a' variable outside the Dijkstra's while, and deleted 'b' variable, which can be obtained by looking at 'dis' array

AC

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

    Thanks , Sir

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

    Hi I was facing similar problem. When I used struct instead of pair as you suggested, I got AC, but can you please tell me why this is happening ? (Why pair is taking so much time?) @gfonn

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

      Now that I see it again, probably it wasn't pair's problem. It might be because he didn't take arguments by reference and read-only in cmp class. That might slow things down a lot. Notice that in my submission I do take arguments like this:

      bool operator<(const arista &a, const arista &b) { return a.second > b.second; }

      So it might be it, i guess.

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

        can you please explain, what is this function doing

        bool operator<(const arista &a, const arista &b) { return a.second > b.second; }

        I got AC after using this comparator and my own struct.

        EDIT: if I use only this comparator function and use pair then I am again getting TLE, but after using struct I got AC

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

          It defines the behavior of comparing two structs arista (using the less-than operator <) Another application is, lets say, you have a struct with a student's data (first and last name, birthdate, average mark, etc). Let's say you want to compare two students a & b, by average mark. One is "less" than the other if it has less average mark. So, you do this:

          bool operator<(const student &a, const student &b) { return a.averageMark < b.averageMark;}

          And you can nest any amount of conditions to determine who's less (define your criterion).

          Priority_queue in C++ uses this operator<, so you need to define it for the struct. BUT if you define the operator< as normally one would do, the priority_queue will give you the greatest first. So to reverse that ordering, you simply trick the priority_queue by reversing the behaviour of your comparator function. So you make it order the wrong way so priority_queue will show the order Dijkstra's need

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

Auto comment: topic has been updated by nipul1 (previous revision, new revision, compare).

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

I think it's better to use actually implemented comparators. If you want to reverse priority queue to be min heap, you should declare it as follows: priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>.

→ Ответить
»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Check My Code 49660585

→ Ответить