题解
题面描述
给定一个公园中的 N 个景点（编号从 0 到 N−1），以及一个 N×N 的距离矩阵，矩阵中第 i 行第 j 列的元素表示景点 i 到景点 j 的距离，距离为 0 表示不相邻。还有一行标记哪些景点是公园的出入口（用 1 表示是，0 表示否）。最后给定一个入口景点编号 S 和一个出口景点编号 T。要求在允许经过任意其他景点但不需要访问所有景点的前提下，找到从 S 到 T 的最短游园线路，并输出具体经过的景点序列。如果存在多条等长最短路径，则输出按景点序号从小到大最小的那条路径。
思路
- 将景点和距离看作一个无向带权图，节点数为 N，边权由距离矩阵给出。
- 使用 Dijkstra 算法 从起点 S 计算到每个节点的最短距离 dist[i]。
- 为了在距离相同的情况下选择 字典序最小 的路径，我们在松弛操作中不仅维护距离，还需要维护到达该节点的路径序列 path[i]。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
