【算法】最短路算法 Dijkstra 的线段树优化

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

鉴于 STL 的 priority_queue 较慢（真挺慢的），我们用线段树来优化 dijkstra 算法。

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

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

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

单点覆盖，区间求最值。

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

例题：LUOGU – 3371【模板】单源最短路径
传送门=￣ω￣=

代码：

#include <bits/stdc++.h>
#define NS (10005)
#define MS (500005)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),!isdigit(c));
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct N{int l,r,d;}e[40005];
int n,m,s,head[NS],nxt[MS],to[MS],d[MS],cnt=1,dis[MS],pos[NS];
inline void push(int a,int b,int c)
{
    nxt[cnt]=head[a],to[cnt]=b,d[cnt]=c,head[a]=cnt++;
}
inline void build(int l,int r,int a)
{
    e[a].l=l,e[a].r=r,e[a].d=INT_MAX;
    if(l==r){pos[l]=a;return;}
    build(l,(l+r)>>1,a<<1),build(((l+r)>>1)+1,r,a<<1|1);
}
inline int query()
{
    int a=1;
    while(e[a].l!=e[a].r)
        if(e[a<<1].d<e[a<<1|1].d)a<<=1;
        else a<<=1,a|=1;
    return e[a].l;
}
inline void update(int a,int k)
{
    a=pos[a],e[a].d=k;
    while(a>>=1,a)e[a].d=min(e[a<<1].d,e[a<<1|1].d);
}
int main()
{
    IN(n),IN(m),IN(s);
    for(int i=1,a,b,c;i<=m;i++)IN(a),IN(b),IN(c),push(a,b,c);
    for(int i=1;i<=n;i++)dis[i]=INT_MAX;
    dis[s]=0,build(1,n,1),update(s,0);
    for(int i=1,u=s;i<=n;i++)
    {
        if(dis[u]==INT_MAX)break;
        for(int j=head[u];j;j=nxt[j])
            if(dis[to[j]]>dis[u]+d[j])
                dis[to[j]]=dis[u]+d[j],update(to[j],dis[u]+d[j]);
        update(u,INT_MAX),u=query();
    }
    for(int i=1;i<=n;i++)printf("%d ",dis[i]);
    return 0;
}

实测比 stl 确实快了不少。

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