#

#
Traveling Salesman Problem

#
Dennis Shasha

#
Omniheurist Course

#
Computer Science

##
*
Description
*

Given a collection of cities, your job is to have your salesman
visit every city at least once and to do so in the cheapest
way possible.
Salesman must start and end at city 1.
The cities will each have three dimensional coordinates.
The z coordinate varies the least as most cities are at pretty
much the same elevation.
The format will be

cityid, x-coord, y-coord, z-coord

Here is
a typical file.

Your output should simply give a sequence of cities in the order
of visit (one line per city) and the total distance traveled.
Note that you do have to return to your home city.
Distance traveled is calculated based on Euclidean distance.
There will be a list of 1000 cities generated the day of the
contest.

The architect will specify a precise format and then evaluate
each solution.