>

> >

My accepted solution is DP (for all cases, no brute force search).

The basic idea is that because all possible edges satisfy the
triangle inequality, the optimal hamiltonian path cannot cross
itself.  Hence, because of the fact that all the vertices lie on a
convex polygon, there is an implicit ordering of the points (what it
is, I'll let you think) - lending itself to a tabular method (DP).

I am sorry but I can hardly agree with you . this problem is
obviously hamiltonian circuit . And it was proved to be a NP
problem.so DP can not solve it .