Блог пользователя mkmeden

Автор mkmeden, история, 20 месяцев назад, По-английски

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/

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
20 месяцев назад, # |
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.

»
15 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

use visited array to ensure not visit same node again which is already minimum.