小算法题--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 mathINF=1000000class Point:    def __init__(self,x,y,z):        self.x,self.y,self.z=x,y,zdef 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 mprint MinPath_Dis(points)