小算法题--7 勇气的挑战

Problem
给定n个点的坐标(x,y,z),且n<=50,从点1出发,怎么样才能走一条路径,访问每个点一次且仅一次,使走过的距离和最小?

Input
多组数据. 第1行n,然后n行3个整数坐标

Output
每组一行,代表最小权和

Sample Input
3
0 0 0
1 1 0
1 -1 0

Sample Output
3.4

Source
A Great Beloved and My Gate to Freedom

import math
INF=1000000
class Point:
    def __init__(self,x,y,z):
        self.x,self.y,self.z=x,y,z

def Dis(a,b):
    return math.sqrt((a.x-b.x)**2+(a.y-b.y)**2+(a.z-b.z)**2)


points=[Point(0,0,0),Point(1,1,0),Point(1,-1,0)]

def MinPath_Dis(points):
    if len(points)==2:
        return Dis(points[0],points[1])
    s=points[0]
    m=INF
    for i in xrange(1,len(points)-1):
        m=min(m,Dis(s,points[i])+MinPath_Dis(points[i:]+points[1:i]))
    return m

print MinPath_Dis(points)