题解
题面描述
给定一个公园中的 N 个景点（编号从 0 到 N−1），以及一个 N×N 的距离矩阵，矩阵中第 i 行第 j 列的元素表示景点 i 到景点 j 的距离，距离为 0 表示不相邻。还有一行标记哪些景点是公园的出入口（用 1 表示是，0 表示否）。最后给定一个入口景点编号 S 和一个出口景点编号 T。要求在允许经过任意其他景点但不需要访问所有景点的前提下，找到从 S 到 T 的最短游园线路，并输出具体经过的景点序列。如果存在多条等长最短路径，则输出按景点序号从小到大最小的那条路径。
思路
- 将景点和距离看作一个无向带权图，节点数为 N，边权由距离矩阵给出。
- 使用 Dijkstra 算法 从起点 S 计算到每个节点的最短距离 dist[i]。
- 为了在距离相同的情况下选择 字典序最小 的路径，我们在松弛操作中不仅维护距离，还需要维护到达该节点的路径序列 path[i]。
P3280.第2题-游园线路
题目内容
某公园每年都会在新年时举办灯会，由于公园面积很大目各景点分散，希望你设计一条游园线路,从某个指定入口景点开始，到某个指定出口景点结束，使得游园总路程最短。最短路线不需要走完所有的景点，目中间允许经过其他出入口景点而不离开公园。
输入描述
第一行:N，景点个数，景点序号从0开始，N−1结束。2<=N<=15
第二行至第N+1行:是一个N∗N的矩阵，表示各相邻景点之间的距离，距离为0表示不相邻。
第N+2行:该景点是否是公园出入口(1-是，0-否)。
第N+3行:要计算最短线路的入口景点序号和出口景点序号
所有用例的输入确保一定存在符合条件的线路，你无需考虑无解的情况。
输出描述
具体游园线路，如果有多条符合条件的线路，按景点序号从小到大进行排序，输出最短的那个。如果还有多个方案，输出字典序最小的。
样例1
输入
3
0 2 4
2 0 3
4 3 0
1 0 1
0 2
输出
0 2
说明
不难看出线路0−>2是最短的
样例2
输入
4
0 2 0 3
2 0 3 1
0 3 0 4
3 1 4 0
1 0 1 0
0 2
输出
0 1 2
说明
不难看出符合要求的线路:
0−>1−>2,长度为5
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
