p3371 【模板】单源最短路径（弱化版）

这是一道关于单源最短路径的模板题，它是一个弱化版，意味着它相对于其他单源最短路径问题来说比较简单。

单源最短路径问题是指在一个有向图中，给定一个起点，求出从起点到其他所有点的最短路径。这个问题有很多解法，其中比较经典的算法有Dijkstra算法和Bellman-Ford算法。

在这个弱化版的模板中，我们只需要使用Dijkstra算法来解决问题。Dijkstra算法是一种贪心算法，它每次找到当前距离起点最近的一个点，然后更新与这个点相邻的点的距离。通过不断重复这个过程，最终可以求出起点到其他所有点的最短路径。

具体实现时，我们可以使用一个优先队列来维护当前距离起点最近的点。每次从队列中取出一个点，然后遍历与这个点相邻的点，更新它们的距离。如果更新后的距离比原来的距离更小，就将这个点加入队列中，等待后续处理。

总之，这个模板题的主要目的是让我们熟悉单源最短路径问题的基本思路和实现方法。如果我们掌握了这个模板，就可以更好地理解其他更复杂的单源最短路径问题。

相关问题

p4779 【模板】单源最短路径（标准版）

这道题是单源最短路径问题的标准版，需要使用Dijkstra算法或Bellman-Ford算法来解决。

Dijkstra算法是一种贪心算法，通过维护一个距离起点最近的未访问节点的集合，不断更新节点的距离和路径，直到所有节点都被访问。时间复杂度为O(ElogV)，其中E为边数，V为节点数。

Bellman-Ford算法则是一种动态规划算法，通过不断松弛边来更新节点的距离和路径，直到所有节点的距离都不再变化。时间复杂度为O(VE)，其中E为边数，V为节点数。

两种算法各有优缺点，Dijkstra算法适用于稠密图，而Bellman-Ford算法适用于稀疏图和存在负权边的情况。

在实现时，可以使用优先队列来优化Dijkstra算法的时间复杂度，也可以使用SPFA算法来优化Bellman-Ford算法的时间复杂度。