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

Solution

update on 2025.8.12:@ED_Builder Solusion->Solution。

思路

使用博客园效果更佳。

首先，题目说的很明白，这个广为人知的最短路算法就是 SPFA，它死了。这题会专门卡 SPFA，别问我咋知道的，在最劣情况下 SPFA 时间复杂度

O

(

n

×

m

)

O(n\\times m)

O(n×m)，边权没有负数的情况下我们通常使用 dijkstra 算法，而在有负边权的情况下通常使用 ‌Bellman-Ford。

这题和简单版的唯一区别就是简单版可以

O

(

n

2

)

O(n^2)

O(n2)，然而这题需要使用更优的时间复杂度。

dijkstra 的实现过程：

用一个 queue 维护我们可以走到的点，dis[u] 表示从起点走到

u

u

u 点的最短路径，我们每次遍历当前节点

u

u

u 可以走到的节点

v

v

v，若从

u

u

u 走到

v

v

v 节点更优，则更新

v

v

v 的最短路，由于我们可以从

u

u

u 节点走到

v

v

v 节点，将

v

v

v 节点丢入 queue 中。

我们可以举个例子：

n

=

4

,

m

=

4

n=4, m=4

n=4,m=4

初始时没有任何操作。

然后从起点遍历，点

1

1

1 至点

2

2

2 的边权为

2

2

2，先遍历到了点

2

2

2，发现我们从点

1

1

1 到点

2

2

2 最优，则更新从起点到点

2

2

2 的最短路，然后丢入队列。

遍历到了点

3

3

3，点

1

1

1 至点

3

3

3 的边权为

3

3

3，发现我们从点

1

1

1 到点

3

3

3 最优，则更新从起点到点

3

3

3 的最短路，然后丢入队列。

然后点

1

1

1 到不了其他点了，所以将队列的第一个元素点

2

2

2 拿出来进行遍历。

从节点

2

2

2 只能遍历到点

4

4

4，且可以更新最短路，丢入队列。

点

2

2

2 到不了其他点了，所以将队列的第一个元素点

3

3

3 拿出来进行遍历。

从节点

3

3

3 只能遍历到点

4

4

4，原最短路是

6

6

6，然而从点

3

3

3 去点

4

4

4 只要

4

4

4，可以更新最短路，丢入队列。

然后把点

4

4

4 拿出来，不能遍历，跳过。

队列空了，结束。

最终结果：

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

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

上面的过程是 dijkstra 的朴素做法，复杂度

O

(

n

2

)

O(n^2)

O(n2)，所以我们需要堆优化。

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

注意事项：

• 由于我们 $dis$
• 题目是有向边。

代码：

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