这是一份关于“无向有权图最短路径”的题解。 题目解析 这道题目是一个标准的单源最短路径问题。 * 目标：找到从起点 111 到终点 nnn 的最短路径，并输出路径上的节点序列。 * 图的特点：无向图、边权为正整数（w≥1w \ge 1w≥1）。 * 数据规模：n,m≤105n, m \le 10^5n,m≤105。 由于边权均为正数，Dijkstra 算法是解决此问题的最佳选择。我们需要在计算最短距离的同时，记录每个节点的前驱节点，以便最后还原路径。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 解题思路 1. 算法选择： * 使用 Dijkstra 算法配合**优先队列（堆）**优化。 * 时间复杂度为 O((N+M)log⁡N)O((N+M)\log N)O((N+M)logN)，对于 10510^5105 的数据规模是可以接受的。 2. 数据结构： * 邻接表：用于存储图，节省空间。 * 距离数组 dist[]：dist[i] 表示从起点 111 到节点 iii 的当前最短距离，初始化为无穷大，dist[1] = 0。 * 前驱数组 pre[]：pre[i] 记录在最短路径上，节点 iii 的前一个节点是谁。这是还原路径的关键。 3. 路径还原： * 当 Dijkstra 算法结束后，如果 dist[n] 仍然是无穷大，说明无法到达，输出 -1。 * 否则，从终点 nnn 开始，利用 pre[] 数组不断向前回溯直到起点 111，将经过的节点存入列表，最后反转列表输出。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C++ 代码实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 关键点说明 1. dist 数组类型： 由于边权 www 最大为 10610^6106，路径最长可能经过 10510^5105 条边，总距离可能达到 101110^{11}1011，超过了 int 的范围，所以 dist 数组建议使用 long long。 2. pre 数组初始化： pre 数组初始化为 -1。起点 111 的前驱保持为 -1，这作为路径回溯的终止条件。 3. 优先队列优化： 使用 priority_queue 配合 greater 来实现小顶堆，确保每次取出的都是当前距离起点最近的未确定节点。 4. 路径回溯： 从终点 nnn 开始，通过 pre[n] 找到上一个点，直到回溯到 -1。得到的序列是 n→⋯→1n \to \dots \to 1n→⋯→1，所以最后必须使用 reverse 函数将其翻转为 1→⋯→n1 \to \dots \to n1→⋯→n。