I am trying problem Problem using dijkstra algorithm. my submission is submission please tell me where I'm wrong in this .
Thanks in Advanced.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
4 | adamant | 160 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
8 | Dominater069 | 154 |
8 | nor | 154 |
I am trying problem Problem using dijkstra algorithm. my submission is submission please tell me where I'm wrong in this .
Thanks in Advanced.
Name |
---|
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.
Could you please tell me how to fix it and what's the reason behind MLE
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.me/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
Thanks , Sir
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
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.
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
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
Auto comment: topic has been updated by nipul1 (previous revision, new revision, compare).
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>>>.
Thanks for suggesting .I did not knew about it.
Check My Code 49660585
OK