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

鉴于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线段树写,然而我并不会。

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

2 条评论

崔欣 · 2018年2月28日 10:31 上午

看不懂,能再解释一下吗?

    konnyakuxzy · 2018年2月28日 10:41 上午

    啊,就是我们用线段树维护dis数组
    $dis[i]$表示起点到点$i$的最短距离
    迪杰斯特拉就是每次取出最小的$dis[i],i\in [1,n]$且$i$没有被选择过对吧
    所以我们用线段树保存一下区间最小值。
    每次取出区间$[1,n]$中$dis$最小的点,作为当前节点。
    根据迪杰斯特拉的思想,当前节点的$dis$已经最小,不可改变。
    所以由当前节点扩展开来,更新与当前节点相连接的点的$dis$(就是松弛操作,如果从当前节点走到下一个点,能使下一个点的$dis$减少,那就从当前节点走到下一个节点)
    然后在线段树中把当前节点位置的值改成$+\infty$,这样下次在线段树中找$min(dis)$就不会再找到当前节点了(相当于堆优化中的在堆中pop当前节点)
    然后一直循环$n$次,因为一共$n$个节点,每个节点会作为当前节点$1$次
    最后就得到了$dis$数组啦,就做完迪杰斯特拉的过程了QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *