题解

题面描述

给定一个公园中的 $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. 松弛时若新的距离更小，直接更新；若新的距离等于当前最优距离，则比较两个路径序列的字典序，选择更小者。

题目内容

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

输入描述

第一行: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$