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

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

题目描述

给定一张有向图，让你求出从起点

s

出发，到每个点的最短距离。

算法

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

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

定义部分

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

s

出发到这个点的最短距离。

CPP

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

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

CPP

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

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

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

算法步骤

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

流程：

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

以下图为例。

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

以

s

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

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

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

但是，上述过程并没有用到堆优化，所以时间复杂度为

O(n ^ 2)

。

事实上，其时间复杂度瓶颈为寻找结点

x

，这个过程可以用优先队列 priority_queue 优化。优化后均摊时间复杂度为

𝑂((n + m) \log n)

。

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

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

即，每次在第二步中取出的

x

，

dis(x)

已经是起点到

x

的最短路径。

标记是因为，

dis(x)

只能更新别的结点一次，保证时间复杂度。

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

CPP

#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;//完结撒花
}

结尾

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

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

文章操作

题目描述

算法

定义部分

算法步骤

结尾

相关推荐

评论

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