//这可能是所有【算法】分类中最辣鸡的一篇了。

鉴于STL的priority_queue较慢(真挺慢的),我们用线段树来优化dijkstra算法。

dijkstra算法的核心优化是去除每次$O(n)$扫一遍已知的distance数组找到最小值这个过程,改成用某种数据结构来维护已知的distance,每次取最小值。

一般用队来实现这个过程。

因此我们也可以用线段树来实现。

单点覆盖,区间求最值。

很简单的线段树操作,几行搞定。

例题:LUOGU - 3371 【模板】单源最短路径
传送门= ̄ω ̄=

代码:

实测比stl确实快了不少。

听说能用zkw线段树写,然而我并不会。