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

· · 题解

Solution

update on 2025.8.12:@ED_Builder Solusion->Solution。

思路

使用博客园效果更佳。

首先，题目说的很明白，这个广为人知的最短路算法就是 SPFA，它死了。这题会专门卡 SPFA，别问我咋知道的，在最劣情况下 SPFA 时间复杂度 O(n\times m)，边权没有负数的情况下我们通常使用 dijkstra 算法，而在有负边权的情况下通常使用 ‌Bellman-Ford。

这题和简单版的唯一区别就是简单版可以 O(n^2)，然而这题需要使用更优的时间复杂度。

dijkstra 的实现过程：

用一个 queue 维护我们可以走到的点，dis[u] 表示从起点走到 u 点的最短路径，我们每次遍历当前节点 u 可以走到的节点 v，若从 u 走到 v 节点更优，则更新 v 的最短路，由于我们可以从 u 节点走到 v 节点，将 v 节点丢入 queue 中。

我们可以举个例子：

n=4, m=4

1 2 3 4
queue 1
dis 0

初始时没有任何操作。

然后从起点遍历，点 1 至点 2 的边权为 2，先遍历到了点 2，发现我们从点 1 到点 2 最优，则更新从起点到点 2 的最短路，然后丢入队列。

1 2 3 4
queue 2
dis 0 2

遍历到了点 3，点 1 至点 3 的边权为 3，发现我们从点 1 到点 3 最优，则更新从起点到点 3 的最短路，然后丢入队列。

1 2 3 4
queue 2 3
dis 0 2 3

然后点 1 到不了其他点了，所以将队列的第一个元素点 2 拿出来进行遍历。

从节点 2 只能遍历到点 4，且可以更新最短路，丢入队列。

1 2 3 4
queue 3 4
dis 0 2 3 6

点 2 到不了其他点了，所以将队列的第一个元素点 3 拿出来进行遍历。

从节点 3 只能遍历到点 4，原最短路是 6，然而从点 3 去点 4 只要 4，可以更新最短路，丢入队列。

1 2 3 4
queue 4
dis 0 2 3 4

然后把点 4 拿出来，不能遍历，跳过。

队列空了，结束。

最终结果：

1 2 3 4
queue
dis 0 2 3 4

但是为什么不能处理负边权？

因为 dijkstra 基于贪心思想，遍历到一次的节点不会再次更新。

上面的过程是 dijkstra 的朴素做法，复杂度 O(n^2)，所以我们需要堆优化。

由于 dijkstra 是基于贪心的算法，因此我们可以用 priority_queue 优化。

注意事项：

代码：

void dijkstra(int s)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    memset(dis, 0x3f, sizeof(dis)); // 初始化
    dis[s] = 0;
    q.push({dis[s], s}); // 将起点加入队列
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (vis[u]) // 若 u 已访问，跳过
            continue;
        vis[u] = true;                          // 标记为已访问
        for (int j = 0; j < adj[u].size(); j++) // 遍历 u 可以去的所有点
        {
            int v = adj[u][j].to, w = adj[u][j].w;
            if (dis[v] > dis[u] + w) // 若从 u 去 v 更优，更改最短路，丢进队列
            {
                dis[v] = dis[u] + w;
                q.push({dis[v], v});
            }
        }
    }
}