求任意两个城市间的最短距离,为方便问题描述,我们用下图来表示城市间的交通图,其中,图中的空心原点表示城市,边上的数字表示城市间的直达距离。
对上图我们做一些解释如下:
上图中共包含4个城市,城市的名称分别为0,1,2,3(我们统一用数字来表示城市名称),其中城市0到城市1的直达距离为1,城市1到城市2的直达距离为2,城市0和城市3之间因为直达路径,所以无直达距离。
另外,为便于理解,我们假定城市i与城市j的直达距离 等于 城市j到城市i的直达距离
【输入数据】
共三行
第一行是城市的个数N
第二行是是一个N*N的数组A, 用于保存两个城市之间的直达距离,如上图中,若A[1][2]=2表示城市1和城市2之间的距离是2,如果两个城市间没有直达的通路,则该元素的值为-1,如A[0][3] = -1
第三行是两个以空格分隔整数,分别代表两个城市名称。
【输出数据】
共两行
第一行是两个城市间的最短距离
第二行是两个城市间的最短距离所对应的路径
注意:
1. 如果两个城市之间没有路径相同,则直接输出提示信息 unreachable
2. 为便于测试,我们给出的测试数据中不会出现 两个城市间有多个最短路径的情况,即两个城市间的最短路径只可能有1条或者没有。
【输入样例1】
4
0 1 8 -1
1 0 2 -1
8 2 0 -1
-1 -1 -1 0
0 2
【输出样例1】
3 /*城市0到城市2的最短距离是3*/
0 1 2 /*城市0到城市2的最短距离对应的路径是0à1à2*/
【输入样例2】
4
0 1 8 -1
1 0 2 -1
8 2 0 -1
-1 -1 -1 0
0 3
【输出样例2】
unreachable /*城市0到城市3之间无路径可达*/