B3602 [图论与代数结构 202] 最短路问题_2 题解

· · 题解

2021/8/29 Update：修改了题解中的两处错误，并在“链式前向星”部分加上了部分注释、增加了建边函数

1.题意

给出一张有 n 个节点，m 条有向边的图，求 1 号点到图中每个节点的最短路。

2.单源最短路问题

给定一个源点（此题中为 1 号点），求从这个源点到图中每个点的最短路径。

接下来先考虑怎么把这个有向图存下来。

用二维数组（设 a_{i,j} 为点 i 到点 j 的距离，空间复杂度 O(n^2)）存图？肯定不行，题目规定 n\le3\times10^5，妥妥的 MLE。

所以就有了这个东西——

3.链式前向星

链式前向星，是一种利用单向链表存图的数据结构。

那么它长什么样呢？

其实它就是 n 个单向链表，第 i 个单向链表存储从点 i 开始的每条边所指向的点（图中的 to）以及这条边的边权（图中的 weight）。

然后把每个链表的头部用一个 head 数组存起来,如果要遍历某个点开始的所有边，直接写

for(int i=head[x];i;i=next[i])//遍历每一条边

就行了。

那么如何加边呢？

很简单，只需要在链表的头部插入，就像这样：

next[++t]=head[x];//记录后继
to[t]=y;//记录这条边指向的地方
weight[t]=z;//记录边权
head[x]=t;//更新链表头部

存图的问题是解决了，但怎么求最短路呢？

如果用 Dfs 暴搜的话，时间复杂度为 O(n!)，稳稳的 TLE。

用 Floyd（其实就是 DP）来做的话，时间复杂度为 O(n^3)，也会 TLE。

于是，就有了这么一个算法：

4.Dijkstra 求最短路

Dijkstra 单源最短路算法，是一种用贪心实现的最短路算法，只能在边权值均为正的情况下运行。至于为什么只能在边权值为正的情况下运行，等一下会提到。

这里我们用一个 \textit{dis} 数组存储从源点（这里为点 1）到图中每一个点的最短路径长度。

先来看一下算法流程：

初始化，把 \textit{dis}_1（源点到源点本身）设为 0，\textit{dis} 的 其余值设为 \infty；

找到 \textit{dis} 数组的最小值所在的下标 1，将其打上标记，并用点 1 的 \textit{dis} 值去更新它周围的点的 \textit{dis} 值，使得 \textit{dis}_2 更新为 3，\textit{dis}_3 更新为 2，\textit{dis}_5 更新为 6；

这里我把 \textit{dis}_1 的数值以及点 1 标蓝了，是因为这个点的最短路已经被求出来了，所以以后不再更新这个点的 \textit{dis} 值。

至于为什么不再更新这个点的 \textit{dis} 值，等一下讲负边权的时候会讲。（这句话你不已经说过一遍了吗……）

点 2、点 3 和点 5 因为被点 1 成功更新了 \textit{dis} 值，所以我把它们的 \textit{dis} 值标黄了。

点 4 和点 6 由于没有被遍历到，所以我把它们的 \textit{dis} 值标黑了。

找到 \textit{dis} 数组没打过标记的最小值所在的的下标 3，将其打上标记，并用点 3 的 \textit{dis} 值去更新它周围没打过标记的点的 \textit{dis} 值，使得 \textit{dis}_5 更新为 3，\textit{dis}_6 更新为 7。

点 1 因为已经被打上标记了，所以不用更新它的 \textit{dis} 值。

点 2 因为没被点 3 更新到 \textit{dis} 值，所以我这里把他标红了。

找到 \textit{dis} 数组没打过标记的最小值所在的的下标 2，将其打上标记，并用点 2 的 \textit{dis} 值去更新它周围没打过标记的点的 \textit{dis} 值，使得 \textit{dis}_4 更新为 10。

找到 \textit{dis} 数组没打过标记的最小值所在的的下标 5，将其打上标记，并用点 5 的 \textit{dis} 值去更新它周围的没打过标记点的 \textit{dis} 值，然而并没有更新到任何点的 \textit{dis} 值。

找到 \textit{dis} 数组没打过标记的最小值所在的的下标 6，将其打上标记，并用点 6 的 \textit{dis} 值去更新它周围的没打过标记点的 \textit{dis} 值，但仍然没有更新到任何点的 \textit{dis} 值。

另外点 2 到点 6 之间那条边的权值是 8，我画图的时候漏了……

找到 \textit{dis} 数组没打过标记的最小值所在的的下标 4，将其打上标记，并用点 4 的 \textit{dis} 值去更新它周围的没打过标记点的 \textit{dis} 值，结果还是没有更新到任何点的 \textit{dis} 值。

所有的点都已经被打上了标记，算法结束。

为什么这个算法是正确的呢？

因为你把一个点打上标记后，如果这条路不是最短路，那就必须得从其他的地方绕过来，而这样求出来的路的长度一定比用 Dijkstra 求出来的路要长。

除非这条路上有负边权，不然你怎样也不可能让这条路变成最短路。

这就是为什么 Dijkstra 不能跑负权图的原因。（滑稽）

但是题目规定 1\le w\le10^7，没有负边权啊！（哈哈哈）

好的，然后我们就可以开开心心地 AC 了这道题……

了吗？

当然不。

由于 Dijkstra 算法查找 \textit{dis} 值的最小值的下标的时间复杂度为 O(n)，而查找下标时一共要查找 O(n) 次，更新每个节点的 \textit{dis} 值时一共又要 O(m) 次，所以总的时间复杂度为 O(n^2+m)，还是过不了……

那么，怎么优化这个算法呢？

5.Dijkstra算法的优化

注意每次查找最小值的时候时间复杂度都是 O(n) 的，算法的瓶颈就在这里。

那么我们每次就把这些被更新的点扔进某一个神奇数据结构里，之后只要对着这个神奇数据结构问一发：此时 \textit{dis} 数组里没被打上标记的最小值的下标是多少，再把这个点拉出来，把更新后的点扔进去就行了~

那么问题来了这个神奇数据结构叫什么呢？

二叉堆啊！

当把符合要求的那个点弹出堆后，就把其他更新后的点扔进堆中；

由于扔进去的点的 \textit{dis} 值一定比原先在堆里的这个点的 \textit{dis} 值要小（就是长江后浪推前浪），所以原先在堆里的那些点可以不用管它，因此如果这个点已经被弹出过（就是被标记过）就直接跳过。/xyx

时间复杂度为 O(m\log m)，可以通过此题。

至于堆的写法可以参考一下P3378的题解。

6.Code

终于可以上代码了……

不过我这里自己手写了一个堆和一个 pair，实际上也可以用 STL 的 priority_queue，但我不想用……

#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
using namespace std;
const int N=300003,M=5555555;
template<class T>inline void swap(T &x,T &y){T z=x;x=y,y=z;}//交换函数
namespace io{
    inline int Read(){//快速读入数字
        int x=0;
        bool d=0;
        char c=getchar();
        for(;!isdigit(c);c=getchar())if(c=='-')d=1;
        for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
        if(d)x=~x+1;
        return x;
    }
    inline void Print(ll x){//快速输出数字
        if(x){
            if(x<0)x=~x+1,putchar('-');
            short a[22],l;
            for(l=0;x;x/=10)a[++l]=x%10;
            for(;l;--l)putchar(a[l]+48);
        }
        else putchar('0');
        putchar(' ');
    }
}
namespace Classes{
    int nxt[N],to[N],w[N],h[N],t;//链式前向星
    inline void AE(int x,int y,int z){//加边操作
        nxt[++t]=h[x];
        to[t]=y;
        w[t]=z;
        h[x]=t;
    }
    template<class T1,class T2>
    class Pair{//自己手写的pair，也可以用STL的pair
    public:
        T1 x;
        T2 y;
        inline bool operator<(const Pair<T1,T2>b)const{return x==b.x?y<b.y:x<b.x;}//排序函数
    };
    template<class T1,class T2>
    inline Pair<T1,T2> Make_Pair(T1 x,T2 y){//把两个元素做成一个pair
        Pair<T1,T2>a;
        a.x=x,a.y=y;
        return a;
    }
    template<class T>
    class Priority_Queue{//手写堆，也可以用STL的priority_ueue
    private:
        T q[N];
        int l;
        inline void Up(int x){
            int y=x>>1;
            while(y&&q[x]<q[y]){
                swap(q[x],q[y]);
                x=y,y=x>>1;
            }
        }
        inline void Down(int x){
            int y=x<<1;
            while(y<=l){
                if(y<l&&q[y+1]<q[y])++y;
                if(q[y]<q[x])swap(q[x],q[y]),x=y,y=x<<1;
                else break;
            }
        }
    public:
        Priority_Queue(){l=0;}
        inline bool Empty(){return l==0;}
        inline void Clear(){l=0;}
        inline void Push(T x){q[++l]=x,Up(l);}
        inline void Pop(){q[1]=q[l--],Down(1);}
        inline T Top(){return q[1];}
    };
}
using namespace io;
using namespace Classes;
ll d[N];//dis数组，注意一定要开long long
bool b[N];//打标记的数组
Priority_Queue<Pair<ll,int> >q;
inline void Dijkstra(){
    memset(d,63,sizeof(d));//初始化
    d[1]=0;//让源点1的dis值为0
    int x,y,z;
    q.Push(Make_Pair(0ll,1));//把源点插入堆中（假装你已经更新过了源点的dis值）
    while(!q.Empty()){
        x=q.Top().y,q.Pop();
        if(b[x])continue;//如果这个点已经被弹出过就跳过
        b[x]=1;//否则就给它打上标记
        for(int i=h[x];i;i=nxt[i]){
            y=to[i],z=w[i];
            if(d[y]>d[x]+z){//如果这个点的dis值不是最优的
                d[y]=d[x]+z;//更新这个点的dis值
                q.Push(Make_Pair(d[y],y));//把更新后的点插入堆中
            }
        }
    }
}
int main(){
    int n=Read(),m=Read(),x,y,z;
    for(int i=1;i<=m;i++)x=Read(),y=Read(),z=Read(),AE(x,y,z);
    Dijkstra();
    for(int i=1;i<=n;i++)Print(d[i]>=0x3f3f3f3f3f3f3f3fll?-1:d[i]);//三元运算符，如果某个点的dis值没被更新过（就是dis值还是初始化的那个值），直接输出-1
    //否则输出这个点的dis值
    return 0;
}

7.一些闲话

可能会有人就会问了：STL 这么好用，为什么不用 STL 呢？

因为 STL 的堆使用的数组是动态开空间的 vector，而动态开空间又很慢，因此最好能不用 STL 就不用 STL。

另外还有一个叫 SPFA 的最短路算法，时间复杂度为 O(km)，其中 k 为常数，平均值为 2，在随机数据下极快。

那我们为什么不能用 SPFA 做这道题呢？

因为 SPFA 在某些特殊构造的数据下，时间复杂度会从 O(km) 退化成 O(nm)，而此题的 n 和 m 的最大值都为 3\times10^5，因此会超时。

所以 NOI2018 就出了这样一个梗：/doge