### mkmeden's blog

By mkmeden, history, 6 weeks ago,

https://cses.fi/problemset/task/1671/

This is the task and at the first look its obvious that its a standard dijkstra problem, But due to some reason my code is giving TLE for 2 large test cases which I am sure the standard dijkstra code should be able to handle. Can someone take a look at this and provide some insight.

code

• 0

 » 6 weeks ago, # |   0 Auto comment: topic has been updated by mkmeden (previous revision, new revision, compare).
 » 6 weeks ago, # | ← Rev. 5 →   0 You need to upgrade your WHILE cycle. ... auto u = q.top(); q.pop(); int curDist = u.first; if(curDist > dist[u.second]) { continue; } ... without this IF your asymptotic can expand up to O(nm). Because you can add several identical pairs with the same vertex but different weights, but we need to take only the best pair.If you have 2 pair like this: {D1, V} and {D2, V}. When you relax first pair all the relaxations with the second pair are useless if D1 < D2.
•  » » 6 weeks ago, # ^ |   0 oh yes got it ... thanks ..