nipul1's blog

By nipul1, history, 14 months ago,

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

• +3

 » 14 months ago, # |   +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.
•  » » 14 months ago, # ^ |   0 Could you please tell me how to fix it and what's the reason behind MLE
 » 14 months ago, # | ← Rev. 2 →   0 You need to avoid using pair and use your own struct. Here is your code, but I've replaced the pair with struct arista: https://codeforces.com/contest/20/submission/57781763Also note I've declared the 'a' variable outside the Dijkstra's while, and deleted 'b' variable, which can be obtained by looking at 'dis' arrayAC
•  » » 14 months ago, # ^ |   +3 Thanks , Sir
•  » » 7 weeks ago, # ^ | ← 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
•  » » » 7 weeks ago, # ^ |   +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.
•  » » » » 7 weeks ago, # ^ | ← 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
•  » » » » » 7 weeks ago, # ^ |   +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
 » 14 months ago, # |   0 Auto comment: topic has been updated by nipul1 (previous revision, new revision, compare).
 » 14 months ago, # |   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, vector>, greater>>.
•  » » 14 months ago, # ^ |   0 Thanks for suggesting .I did not knew about it.
 » 12 months ago, # | ← Rev. 2 →   +1 Check My Code 49660585
•  » » 12 months ago, # ^ |   0 OK