专栏文章

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

千千花秋雨
P4779题解参与者 6已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@miossfrj
此快照首次捕获于
2025/12/03 00:33
3 个月前
此快照最后确认于
2025/12/03 00:33
3 个月前
查看原文
这题竟然还可以交题解？好神奇。
upd 2025.7.23：一点也不神奇，才知道新加了一个模板题题解规范，根本过不了审啊啊啊。

算法介绍

本题使用堆优化 dijkstra。时间复杂度 O((n+m)log⁡n)O((n+m)\log n)。空间复杂度 O(V+E)O(V+E) 。其中 VV 为节点数，EE 为边数。
Dijkstra 可以解决‌单源最短路径问题‌。前提是要求图中所有边的权重均为非负数，不然会出错。算法可以找到源点到所有可达节点的最短路径。
Dijkstra 的步骤。
  • 初始化所有点没被访问过，并将源点到源点的初始距离设置为 00，其余设置为极大值，方便之后遇到更短路径打擂台。
  • 建立一个优先队列从小到大维护到源点的距离 dd，第二关键字记录一下这个 dd 所对应的节点编号。
  • 队列不空就一直取出存的节点，该节点已被访问就跳过。否则 dv=min⁡(dv,du+wu→v)d_v=\min(d_v,d_u+w_{u\rightarrow v})。
  • 最后再将更新完的 dvd_v 存入队列。

正确性证明

证明：每次从优先队列取出 dud_u 最小的 uu 节点时，其 dud_u 必为最短路径。
反证：若存在更短路径，则该路径必包含某个未处理的节点 xx，且 dx<dud_x < d_u（与 uu 的最小性矛盾）。
所以到了最后一次取出的 dud_u，依旧是最短路。
‌松弛操作‌：对 uu 的邻居 vv，若 du+wu→v<dvd_u + w_{u\rightarrow v} < d_v，则更新 dvd_v，保证其始终为当前最短路径。

代码实现

先用链式前向星建图。
CPP
struct node{
	int nxt,to,dis;
}e[M];
void add(int u,int v,int w){
	e[++cnt].nxt=h[u];  //nxt: 与当前边同起点的上条边的编号‌
	e[cnt].to=v;   //to: 这条边的到点
	e[cnt].dis=w;  //dis: 边权
	h[u]=cnt;    //h[u]: 节点 u 为起点的最后一条边
}
//想建 u->v 权值为 w 的边就调用 add(u,v,w)
整理一下框架，按题目建图得到以下代码。
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;i++)
const int N=1e5+10;
const int M=2e5+10;
int n,m,s;
int h[N],cnt;
struct node{
	int nxt,to,dis;
}e[M];
void add(int u,int v,int w){
	e[++cnt].nxt=h[u];
	e[cnt].to=v;
	e[cnt].dis=w;
	h[u]=cnt;
}
ll d[N];//d[i]: s->i 的距离 
void dij(int s){//计算的是到节点 s 的距离 
	
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>s;
	while(m--){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	dij(s);
	For(i,1,n)cout<<d[i];
	return 0;
}
现在考虑怎么写 dij 即可。
CPP
ll d[N];//d[i]: s->i 的距离 
bool vis[N];
priority_queue<pair<ll,int> >q;
//第一关键字存放距离，第二关键字存放这是哪个节点的 d
void dij(int s){//计算的是到节点 s 的距离 
	For(i,1,n){//初始化
		vis[i]=0;//都没有被访问
		d[i]=1e18;//距离初始化成极大值，从而遇到更小的就能更新
        /*如果初始化为比较小的值，实际的最小 d 就可能比初始化的
        值还大，那么结果就一直是初始值*/
	}
	d[s]=0;// s—>s 距离为 0
	q.push(make_pair(0,s));  //放入初始的距离 d 和节点 s
	while(!q.empty()){
		int u=q.top().second;  //取出存放的节点
		q.pop();  //取出了就弹掉
		if(vis[u])continue;  //之前已经访问过（即已经更新过了）就跳过
		vis[u]=1;   //标记已访问
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].to;   //第 i 条边的到点
			int w=e[i].dis;  //第 i 条边的权值
            /*对于 u—>v 这条路，总花费为 s—>u 的最短路 + u—>v 的边权
            也就是 d[u]+w。如果这样走比原来的走法更小，那就更新。*/
			if(d[v]>d[u]+w){  
				d[v]=d[u]+w;
				q.push(make_pair(-d[v],v));//更新完把新的边权和节点放进去
                /*由于 priority_queue 是从大到小排序，我们希望从小到大排序
                 所以放个相反数进去，刚刚好可以正常排序
			}
		}
	}
}
综上得到完整代码。
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;i++)
const int N=1e5+10;
const int M=2e5+10;
int n,m,s;
int h[N],cnt;
struct node{
	int nxt,to,dis;
}e[M];
void add(int u,int v,int w){
	e[++cnt].nxt=h[u];
	e[cnt].to=v;
	e[cnt].dis=w;
	h[u]=cnt;
}
ll d[N];//d[i]: s->i 的距离 
bool vis[N];
priority_queue<pair<int,int> >q; 
void dij(int s){//计算的是到节点 s 的距离 
	For(i,1,n){
		vis[i]=0;
		d[i]=1e18;
	}
	d[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(int i=h[u];i;i=e[i].nxt){
			int v=e[i].to;
			int w=e[i].dis;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				q.push(make_pair(-d[v],v));
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m>>s;
	while(m--){
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
	}
	dij(s);
	For(i,1,n)cout<<d[i]<<" ";
	return 0;
}
一些问答。
Q：dd 为什么要在堆里从小到大排序？
A：Dijkstra 基于贪心原则：‌当前距离起点最近的节点，其最短路径已确定‌。最小堆保证每次取出的节点符合这一条件，避免无效遍历。
Q：不连通出发点 ss 的节点 xx 会返回什么 dxd_x？
A：返回初始化赋的极大值。

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...