nipul1's blog

[SOLVED] Why getting TLE in dijkstra straight forward implementation ?
By nipul1, history, 5 years ago, In English

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

Thanks in Advanced.

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

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

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.

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

    Could you please tell me how to fix it and what's the reason behind MLE

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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://codeforces.net/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

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

    Thanks , Sir

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

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

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

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

          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

          → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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>>>.

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

    Thanks for suggesting .I did not knew about it.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Check My Code 49660585

→ Reply