会员专享
请先
登录 ，登录后可使用今日免费解锁；
开通会员 后可解锁完整内容。
题解
题面描述
给定一个公园中的 N N N 0 0 0 N − 1 N-1 N − 1 N × N N\times N N × N i i i j j j i i i j j j 0 0 0 1 1 1 0 0 0 S S S T T T S S S T T T
思路
将景点和距离看作一个无向带权图，节点数为 N N N
使用 Dijkstra 算法 从起点 S S S d i s t [ i ] dist[i] d i s t [ i ]
为了在距离相同的情况下选择 字典序最小 的路径，我们在松弛操作中不仅维护距离，还需要维护到达该节点的路径序列 p a t h [ i ] path[i] p a t h [ i ]
题目内容
某公园每年新年都会举办灯会，园内景点数量较多且位置分散。现在需要规划一条游园路线：从某个指定的入口景点开始，到某个指定的出口景点结束，目标是让路线中依次经过的相邻景点路程之和尽可能小。
这条路线不需要游览全部景点；途中经过其他出入口景点时，不视为离开公园。
景点之间的可达关系与路程由一个距离矩阵描述：矩阵中的某个值为 0 表示对应的两个景点不相邻；若为非 0，则表示这两个景点相邻，且该值就是它们之间的路程。所有景点编号为从 0 到 N-1。
如果存在多条总路程并列最短的路线，则需要选择景点编号序列字典序最小的一条。
约束条件：
景点个数 N 满足 2 ≤ N ≤ 15 2 \le N \le 15 2 ≤ N ≤ 15
输入描述
第一行包含一个整数 N，表示景点总数。
接下来 N 行，每行包含 N 个整数，构成距离矩阵。其中第 i 行第 j 列的整数表示景点 i 与景点 j 之间的路程，0 表示两者不相邻。
随后一行包含 N 个整数，第 i 个整数表示景点 i 是否为公园出入口，1 表示是，0 表示否。
最后一行包含两个整数 S 和 T，分别表示指定的入口景点编号和出口景点编号。
输入保证至少存在一条从 S 到 T 的可行路线。
输出描述
输出一行，给出从入口景点 S 到出口景点 T 的游园路线。按游览顺序输出经过的景点编号，编号之间用单个空格分隔。
如果有多条总路程最短的路线，则输出景点编号序列字典序最小的一条。
样例1
输入
4
0 1 2 0
1 0 0 3
2 0 0 2
0 3 2 0
1 0 0 1
0 3
输出
0 1 3
说明
如图：
样例2
输入
2
0 7
7 0
1 1
0 1
输出
0 1
说明
景点数量为 2 2 2 0 和出口景点 1 之间只有一条相邻边，边权为 7 7 7
因此唯一可行路线为 0 → 1，总路程为 7 7 7
样例3
输入
5
0 4 2 0 20
4 0 0 0 3
2 0 0 2 0
0 0 2 0 4
20 3 0 4 0
1 1 0 0 1
0 4
输出
0 1 4
说明
如图：
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
