题目内容

某公园每年都会在新年时举办灯会，由于公园面积很大目各景点分散，希望你设计一条游园线路,从某个指定入口景点开始，到某个指定出口景点结束，使得游园总路程最短。最短路线不需要走完所有的景点，目中间允许经过其他出入口景点而不离开公园。

输入描述

第一行:N，景点个数，景点序号从$0$开始，$N-1$结束。$2<=N<=15$

题解

题面描述

给定一个公园中的 $N$ 个景点（编号从 $0$ 到 $N-1$），以及一个 $N\times N$ 的距离矩阵，矩阵中第 $i$ 行第 $j$ 列的元素表示景点 $i$ 到景点 $j$ 的距离，距离为 $0$ 表示不相邻。还有一行标记哪些景点是公园的出入口（用 $1$ 表示是，$0$ 表示否）。最后给定一个入口景点编号 $S$ 和一个出口景点编号 $T$。要求在允许经过任意其他景点但不需要访问所有景点的前提下，找到从 $S$ 到 $T$ 的最短游园线路，并输出具体经过的景点序列。如果存在多条等长最短路径，则输出按景点序号从小到大最小的那条路径。

思路

1. 将景点和距离看作一个无向带权图，节点数为 $N$，边权由距离矩阵给出。
2. 使用 Dijkstra 算法 从起点 $S$ 计算到每个节点的最短距离 $dist[i]$。
3. 为了在距离相同的情况下选择 字典序最小 的路径，我们在松弛操作中不仅维护距离，还需要维护到达该节点的路径序列 $path[i]$。
4. 松弛时若新的距离更小，直接更新；若新的距离等于当前最优距离，则比较两个路径序列的字典序，选择更小者。