Solution

update on 2025.8.12:ED_BuilderSolusion->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 优化。

注意事项：

由于我们 $dis$ 要取 $\min$ 值，所以 $dis$ 初始化为一个极大值，通常为 $\inf$ 。
题目是有向边。

代码：

CPP

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});
            }
        }
    }
}

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

文章操作

Solution

思路

相关推荐

评论

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