一道动态规划编程题，请用C或C++解决，感谢问题描述求任意两个城市间的最短距离，为方便问题描述，我们用下图来表示城市间的交通图，其中，图中的空心原点表示城市，边上的数字

Question

一道动态规划编程题，请用C或C++解决，感谢
【问题描述】
求任意两个城市间的最短距离，为方便问题描述，我们用下图来表示城市间的交通图，其中，图中的空心原点表示城市，边上的数字表示城市间的直达距离。

对上图我们做一些解释如下：
上图中共包含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之间无路径可达*/

Answer 1

单源最短路径：Dijkstra算法
任意两点最短路径：Floyd 算法
随便一本算法书上都会有的