Question

一道动态规划的编程题，请用C或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

是图论题吧........
这个可以用Floyd-Warshall 算法
具体可以看http://www.nocow.cn/index.php/Floyd-Warshall%E7%AE%97%E6%B3%95
网上介绍的很多,这个算法就是用DP的

Answer 2

最小生成树。过两天写。留个记号