5

Shortest route 1 | CSES

 1 year ago
source link: http://codeforces.com/blog/entry/105908
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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/

6 hours 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.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK