UVA Getting in Line(二)

2015-07-20 18:07:09 · 作者: · 浏览: 18
********************** Network #3 Cable requirement to connect (132,73) to (72,111) is 87.02 feet. Cable requirement to connect (72,111) to (49,86) is 49.97 feet. Number of feet of cable required is 136.99.

求连接几个点的一条有向路,使得路长最短。

由于数据较小,可以枚举几个点的全排列,分别算出路长,再求最小的那个。也可以用DFS+回溯,是更一般的方法,这个方法中用一个数组S记录节点的位置,避免设置麻烦的答案数组。

AC代码如下:

?


?

?