题解：P4779 【模板】单源最短路径（标准版）

· · 题解

这道题很显然是 Dijkstra 的板子题

题目描述

给定一张有向图，让你求出从起点 s 出发，到每个点的最短距离。

算法

这道题应该使用堆优化的 Dijkstra 吧，如果不会没有堆优化的 Dijkstra 的话，请转至 P3371 。

Dijkstra 一定是在没有负边权的图上使用，具体的后面讲。

定义部分

毕竟是堆优化，我们肯定要定义一个堆，就是priority_queue，他叫优先队列。他就是一个二叉堆。但是只定义一个可不行，我们需要建立一个结构体，里面是节点编号以及到从 s 出发到这个点的最短距离。

struct node{
    long long id, dis;
};
bool operator <(const node &x, const node &y){
    return y.dis<x.dis;//排序
}
priority_queue<node> q;

还有一个 vector，这个就很常规了。

struct E{
    long long v, w;
};
vector<E> e[N];

然后是一个记录距离，也就是答案的数组 dis。

其他的就是题目里要求的啦。

算法步骤

主要思想就是，我们找当前节点的所有出边，如果找到一个比当前答案更优的答案，就改变当前答案。

流程：

  1. 初始化 dis[s] 为零，其他 dis 为无穷大。
  2. 在未被标记的点中找到 dis[x] 最小的 x，并标记结点 x。
  3. 扫描 x 的所有出边 (x,y,z)，如果 dis(y) > dis(x) + z，则更新 dis(y)。
  4. 重复步骤二到三直至所有结点被标记。

以下图为例。

为了方便，我们用字母表示边的编号，括号内的数字表示边权。

以 s 为一为例，前面初始化省去。

  1. 看 a，边权为一，显然小于节点二的答案，更新节点二的答案。
  2. 看 b，边权为一，更新节点三答案。
  3. 遍历到了节点二，看 c，边权为三，更新节点四的答案。
  4. 遍历到了节点三，看 d，边权为二，更新节点五的答案。
  5. 遍历到了节点四，看 e，边权为四，不更新节点五的答案。

这样，我们就把这张图遍历完了。

但是，上述过程并没有用到堆优化，所以时间复杂度为 O(n ^ 2)。

事实上，其时间复杂度瓶颈为寻找结点 x，这个过程可以用优先队列 priority_queue 优化。 优化后均摊时间复杂度为 𝑂((n + m) \log n)。

还记得前文中说 Dijkstra 不能处理负边权吗，这里解释一下。

其思想基于贪心：当边长为非负数，全局最小值必然不可 能再被更新。

即，每次在第二步中取出的 x，dis(x) 已经是起点到 x 的最短路径。

标记是因为，dis(x) 只能更新别的结点一次，保证时间复杂度。

好了，该讲的都讲完了，现在上代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long n, m, s;
long long u, v, w;
long long dis[N];
struct E{
    long long v, w;//边的终点和权值
};
struct node{
    long long id, dis;//节点编号和距离
};
bool operator <(const node &x, const node &y){
    return y.dis<x.dis;//优先队列按距离从大到小排序
}
vector<E> e[N];
priority_queue<node> q;
void Dijkstra(int s){
    for(int i=1;i<=n;i++)
        dis[i]=1e18;//初始化距离
    dis[s]=0;//源点距离为0
    q.push({s,0});//入队
    while(!q.empty()){
        node now=q.top();//取出队首元素
        q.pop();//弹出队顶
        int u=now.id;//当前节点
        if(now.dis>dis[u]) continue;//小优化
        for(auto v:e[u]){//遍历当前节点的出边
            if(dis[v.v]>dis[u]+v.w){//更新距离
                dis[v.v]=dis[u]+v.w;///更新距离
                q.push({v.v, dis[v.v]});//入队
            }
        }
    }
    return;
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        e[u].push_back({v,w});//建边
    }
    Dijkstra(s);//计算最短路
    for(int i=1;i<=n;i++)//输出答案
        cout<<dis[i]<<" ";
    return 0;//完结撒花
}

结尾

这篇题解写的可能有点乱，希望大家见谅。