警示后人

P4779 【模板】单源最短路径(标准版)

WhisperingWillow @ 2024-08-17 16:28:39

虽然我过了这题(900+ms)。但是我的 DIJ 算法在其他地方被卡了。

如果你的 dij 是这么写的:

while(){
 vis[x] = 1;
 ...
 if(!vis[y]) q.push(y);
}

可能你的队列是这样的

每个 $x,y,z$ 都会被执行一遍,然后套娃。 这样复杂度可能退化成 $\mathcal O(n^2\log n)$ 的。

by MrPython @ 2024-08-18 17:49:49

这是 bfs 的常见错误吧

我记得小时候寄过好多次


|