### mkmeden's blog

By mkmeden, history, 6 weeks ago,

 » 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.