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

· · 题解

题目思路

SPFA 在最坏情况下的时间复杂度为 \mathcal O(nm)，因此我们需要更快的最短路算法。这里介绍 Dijkstra 算法。

Dijkstra 本质上是一种贪心。我们将所有结点分成两种集合，分别是已经确定最短路的点集和没有确定最短路的点集。

我们定义 d_i 为从点 s 到点 i 的最短路长度。最开始时 d_s 为 0，其余所有的 d_i 为无穷大。

接着对于当前已经确定的点，寻找未确定的点中与其连边最短的，对它执行松弛操作，这下这个点也能进入已经确定最短路的点集了。然后这个点就成为了当前已确定的点，我们可以回到这步操作的开头重新进行此操作直到所有点都确定了最短路。

朴素的实现需要暴力寻找最短路长度最小的点，所以复杂度为 \mathcal O(n^2)，显然还不够快。考虑使用堆优化，每次松弛完边都将其插入堆中，需要找到最短路长度最小的边直接取堆顶即可。

可以用优先队列维护，插入操作的复杂度为 \mathcal O(\log n)，删除操作的复杂度同样为 \mathcal O(\log n)，取堆顶为 \mathcal O(1)，所以总复杂度为 O((n + m) \log n)。

正确性说明

可以看出，每次选择的最近点不会再被更新。如果走其他路，必须经过某个比目前长度更远的点加上新走的路的权值，因为所有权值都是大于等于 0 的，所以只会更长，不可能更短。

此外请注意，如果存在负权值，那么此贪心思路并不成立，所以 dijkstra 只能用于求解非负权图上的单源最短路径问题，如果要处理负权值，还需要使用 SPFA。

AC 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,s,dis[100010];
bool vis[100010];
struct Edge{
    int to,w;
    bool operator < (const Edge &other) const{
        return w > other.w;
    }
};
vector<Edge> g[200010];
priority_queue<Edge> q;
void dijkstra(int s){
    for(int i = 1;i <= n;i++) dis[i] = INT_MAX;
    q.push({s,0});
    dis[s] = 0;
    while(!q.empty()){
        Edge now = q.top();
        q.pop();
        int u = now.to;
        if(vis[u]) continue; 
        vis[u] = true;
        for(auto v:g[u]){
            if(dis[v.to] > dis[u] + v.w){
                dis[v.to] = dis[u] + v.w;
                q.push({v.to,dis[v.to]});
            }
        }
    }
}
int main(){
    cin >> n >> m >> s;
    for(int i = 1;i <= m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        g[u].push_back({v,w});
    }
    dijkstra(s);
    for(int i = 1;i <= n;i++) cout << dis[i] << " ";
    cout << endl;
    return 0;
}