题目内容

某公园每年新年都会举办灯会，园内景点数量较多且位置分散。现在需要规划一条游园路线：从某个指定的入口景点开始，到某个指定的出口景点结束，目标是让路线中依次经过的相邻景点路程之和尽可能小。

这条路线不需要游览全部景点；途中经过其他出入口景点时，不视为离开公园。

景点之间的可达关系与路程由一个距离矩阵描述：矩阵中的某个值为 0 表示对应的两个景点不相邻；若为非 0，则表示这两个景点相邻，且该值就是它们之间的路程。所有景点编号为从 0 到 N-1。

如果存在多条总路程并列最短的路线，则需要选择景点编号序列字典序最小的一条。

约束条件：

• 景点个数 N 满足 $2 \le N \le 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$，入口景点 0 和出口景点 1 之间只有一条相邻边，边权为 $7$。

因此唯一可行路线为 0 → 1，总路程为 $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.逐行代码手写