一道动态规划的编程题,请用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之间无路径可达*/

是图论题吧........
这个可以用Floyd-Warshall 算法
具体可以看http://www.nocow.cn/index.php/Floyd-Warshall%E7%AE%97%E6%B3%95
网上介绍的很多,这个算法就是用DP的
温馨提示:答案为网友推荐,仅供参考
第1个回答  2010-12-29
最小生成树。过两天写。留个记号
相似回答
大家正在搜