SeleznevS1's blog

Solution gets TLE, because dijkstra is too slow for some reason. please help!
By SeleznevS1, history, 9 months ago, In English

I was recently solving problem 449B and came up with a solution involving Dijkstra's algorithm. I implemented it using priority_queue, got TLE17, switched to set and got TLE45. I'm using a straightforward dijkstra and constraints are m=4*10^5, n = 10^5. Dijkstra's complexity is MlogN, so I expected it to pass. Is dijkstra really that slow? thank you in advance!

Here's the problem: https://mirror.codeforces.com/problemset/problem/449/B Here's the submission: https://mirror.codeforces.com/contest/449/submission/330250374

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

»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

You should ignore duplicate entries of the same node with worse distance values. Currently, you're processing all 'v's that are pushed even though the shortest path to those nodes might have already been processed, and hence they are useless for further computations. Just include a check for the current_weight to not be larger than dist[v] and I think you should be good to go.

→ Reply
»
9 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

You have implemented the dijkstra incorrectly using set.

There is one mistake here, you do not delete the previous value from set when updating.

The error is in lines

62, 63

dist[u] = current_weight + weight;
s.insert({dist[u], u});

If implemented correctly it should be

s.erase({dist[u],u});
dist[u] = current_weight + weight;
s.insert({dist[u], u});.

And then the task will pass, and it will not go unnecessary times. Here is the corrected solution

→ Reply