mkmeden's blog

By mkmeden, history, 6 weeks ago, In English

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

Failing TCs : https://cses.fi/file/6202e05529aba02706fe1c03ec7d07ed68c2e254b69047129b52185f875b9a1e/1/1/ https://cses.fi/file/a563cff68cf3d8ade012345cf49bc668cdb1f02f7a75317091066f81c0db16d5/1/1/

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

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.