Traveling Salesman in polynomial time
- by Andres
Problem Description:
Write a program in any language with the shortest number of characters that solves the following problem:
Given a collection of cities and the cost of travel between each pair of them, find the cheapest way of visiting all of the cities and returning to your starting point. All solutions must take at most polynomial time.
Input will be in the form of a text file named simply "i". The text file will contain data in the following format:
city1# city2# cost$
cityA# cityB# cost$
...
Each element in the file is separated with a space, and there is a newline at the end of every line.
Code count does not include whitespace.
Solutions that take longer than polynomial time to find will not be accepted
