LOJ6354 & 洛谷4366：[Code+#4]最短路——题解

这道题需要使用 Dijkstra 算法来解决。

Dijkstra 算法是一种贪心算法，用于解决没有负权边的单源最短路径问题。算法的基本思想是：从源点开始，每次选择当前最短路径的节点，并更新其周围节点的距离。

具体步骤如下：

1. 初始化距离数组 dist，将源点到自己的距离设为 0，其他点到源点的距离设为无穷大。

2. 创建一个集合 visited，用于存储已经确定最短路径的节点。

3. 将源点加入 visited 集合中。

4. 对于源点周围的每个节点，更新它们到源点的距离。如果距离更短，则更新 dist 数组。

5. 从 dist 数组中选择距离最短的节点，将其加入 visited 集合中。

6. 重复第 4 步和第 5 步，直到所有节点都被加入 visited 集合中。

7. dist 数组中的值即为源点到每个节点的最短距离。

注意事项：

1. Dijkstra 算法只适用于没有负权边的图。

2. Dijkstra 算法不能处理有向无环图中的负权边。

下面是 Python 代码实现：