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

matrixPower · 2025-07-21 19:58:20 · 题解

传送门

算法介绍

最短路问题（SPP，Shortest Path Problem），是指在一个‌加权图‌中寻找两个顶点之间‌路径权值和最小‌的路径。即给定一个图 G=(U,V)，和边权 w(e)，给出起点 s 终点 t，求出一条路径 P，使得 \sum _{e\in P} w(e) 最小，并求出这个值。

这个算法有两个非常经典的实现：Dijkstra 算法和 SPFA 算法。

算法流程

Dijkstra 算法

先说结论：每次选出 1\sim n 中没被选出且距原点距离最小的点，在让其更新与之连接的点。

正确性证明

~~其实就是将网上那些博客写的通俗了些。~~

使用归纳法。

当只有一个节点时，取出这一个节点，显然满足命题。

假设现在访问的节点的距离皆为最小距离。

当我们在查找另外一个没有访问的且其距离最小节点，显然原点至此点的最短路径上没有没被访问过的节点（我的个人理解是，如果出现了没被访问过的节点，那么这个点一定没有被计算过，其值一定为无限大），在查找一个与其联通的点 u，现在会出现两种情况：

点 u 已经被访问过。
点 u 未被访问过。

对于第一种情况，u 被访问过，其已经是最短路径。

对于第二种情况，我们拿原先的点的距离加上边权去更新点 u，让其变成最小值。

综上两种情况，点 u 都成为了最小值，证明这一步更新之后，所有点都成为了最小值。那么下一步之后，肯定也是最小值。所以每一步皆为最小值。

证毕。

代码实践

设原点为 1，我们每次 O(n) 寻找距原点最小的一个没被访问过的点，将这个点设为已访问，去遍历他的后继节点，进行更改操作。

dis[1]=0;
for(int i=1;i<=n;i++)
{
    int x;
    ll sum=1e18;
    for(int j=1;j<=n;j++)
    {
        if(b[j]) continue;
        if(sum>dis[j]) sum=dis[j],x=j;
    }
    b[x]=1;
    for(int j=0;j<a[x].size();j++)
    {
        int v=a[x][j].first,w=a[x][j].second;
        if(dis[v]>dis[x]+w) dis[v]=dis[x]+w;
    }
}

易得时间复杂度 O(n^2)。

一点优化

显然，每次 O(n) 查询距离最小节点有点耗时，那有什么快速排序的东西呢？set？不行，会去重。

这时候就可以拿出优先队列（priority_queue）了。这是一个可以进行插入、删除、排序（默认从大到小）等操作的 STL。简单用途如下：

定义：priority_queue<变量类型,vector<变量类型>>，排序顺序为从大到小；priority_queue<变量类型,vector<变量类型>,greater<变量类型>>排序顺序为从小到大。
插入：push(a) 操作。
删除：pop() 操作。注意：删除最大/小的！
查找顶端：front() 操作。

实例：

priority_queue<int,vector<int>,greater<int>>q;
q.push(114);;
q.push(78);
q.push(514);
int x=q.front();q.pop();
cout<<x<<endl;
x=q.front(),q.pop();
cout<<x<<endl;
cout<<q.front()<<endl;

程序输出

78
114
514

优化的代码：

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
pq.push({0,s});
while(!pq.empty())
{
    int id=pq.top().second;ll sum=pq.top().first;pq.pop();
    if(b[id]) continue;
    b[id]=1;
    for(int j=0;j<a[id].size();j++)
    {
        if(dis[a[id][j].first]>dis[id]+a[id][j].second)
        {
            dis[a[id][j].first]=dis[id]+a[id][j].second;
            pq.push({dis[a[id][j].first],a[id][j].first});
        }
    }   
}

注意：一定要把距离放在 pair 第一位，因为 pair 在排序时优先比较第一位。

时间复杂度：每次插入 \log，最多有 m 条边，所以一次插入 \log m，最多会有 m 跳边被插入，所以时间复杂度为 O(m \log m)。

SPFA 算法

~~时间复杂度略高，此题过不了，如有兴趣可以去学习 P3371。~~

虽然过不了，但是很有用处（SPFA 算法可以处理带有负环的图，但 Dijkstra 不行）。

大致流程类似 BFS，将所有更改过的点加入队列，注意现在在队中的点不可加入。每次取出一个点，去更新它的后继。时间复杂度 O(nk)，k 为不定常数，最慢可卡为 O(nm)。

可以观察到，每个点最多只会被更新 n-1 次（每个点都要更新他），如果一个点更新了 n 次，证明存在负环。

SPFA 算法的推广：差分约束

参考 P5960。

可以观察到每个不等式跟两个算法中更新最小值过程类似，所以可以使用这两个算法来计算，但这种题一般都有负环，所以我们常用 SPFA 算法。

例题

很少，就一道，就是本题。

观察到 1 \le n \le 10^5，1 \le m \le 2\times 10^5，SPFA 不可过，所以我们使用 Dijkstra 算法。

注意要将原点至原点的距离设为 0，其余值为无限大。

#include<bits/stdc++.h>
#define endl '\n' 
#define small priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >
using namespace std;

typedef long long ll;
typedef double db;
const db eqs=1e-6;
const int inf=1e9;
void cmin(int &a,int b){a=min(a,b);}
void cmax(int &a,int b){a=max(a,b);}
bool db_eq(db a,db b){return fabs(a-b)<eqs;}

const int MAXN=100000+5;  
int n,m,s,t,b[MAXN];
ll dis[MAXN];
vector<pair<int,int> >a[MAXN];
small pq;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++) dis[i]=1e18;
    dis[s]=0;
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        a[x].push_back(make_pair(y,z));
    }
    pq.push({0,s});
    while(!pq.empty())
    {
        int id=pq.top().second;ll sum=pq.top().first;pq.pop();
        if(b[id]) continue;
        b[id]=1;
        for(int j=0;j<a[id].size();j++)
        {
            if(dis[a[id][j].first]>dis[id]+a[id][j].second)
            {
                dis[a[id][j].first]=dis[id]+a[id][j].second;
                pq.push({dis[a[id][j].first],a[id][j].first});
            }
        }   
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0;
}