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

· · 题解

这题竟然还可以交题解？好神奇。

upd 2025.7.23：一点也不神奇，才知道新加了一个模板题题解规范，根本过不了审啊啊啊。

算法介绍

本题使用堆优化 dijkstra。时间复杂度 O((n+m)\log n)。空间复杂度 O(V+E) 。其中 V 为节点数，E 为边数。

Dijkstra 可以解决‌单源最短路径问题‌。前提是要求图中所有边的权重均为非负数，不然会出错。算法可以找到源点到所有可达节点的最短路径。

Dijkstra 的步骤。

正确性证明

证明：每次从优先队列取出 d_u 最小的 u 节点时，其 d_u 必为最短路径。

反证：若存在更短路径，则该路径必包含某个未处理的节点 x，且 d_x < d_u（与 u 的最小性矛盾）。

所以到了最后一次取出的 d_u，依旧是最短路。

‌松弛操作‌：对 u 的邻居 v，若 d_u + w_{u\rightarrow v} < d_v，则更新 d_v，保证其始终为当前最短路径。

代码实现

先用链式前向星建图。

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)

整理一下框架，按题目建图得到以下代码。

#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 即可。

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 是从大到小排序，我们希望从小到大排序
                 所以放个相反数进去，刚刚好可以正常排序
            }
        }
    }
}

综上得到完整代码。

#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：d 为什么要在堆里从小到大排序？

A：Dijkstra 基于贪心原则：‌当前距离起点最近的节点，其最短路径已确定‌。最小堆保证每次取出的节点符合这一条件，避免无效遍历。

Q：不连通出发点 s 的节点 x 会返回什么 d_x？

A：返回初始化赋的极大值。