The Euclidean problem TSP (Travel Salesman Problem) in Python.

We have a set of points forming a graph.

Input format:

The first line contains an integer n - the number of points in the plane n≤500.

Subsequent n lines contain co-ordinates of points: each line contains a triple of numbers

(p_i,,x_i,,y_i), where p_i is unique identifier of a point (an integer), and x_i and y_iy are

coordinates of point p_i (both are floating point numbers).

Example:

4

1 0.0 0.0

2 1.0 0.0

3 1.0 1.0

4 0.0 1.0

Output format:

A single line, in which the point identifiers are listed separated by a space. The last of the

identifiers must be the same as the first (route closed), the others are not repeated.

Example:

12341

Write Python script for solving this problem. Do not use special libraries to solve TSP (like python-

tsp). Other libraries (e.g. numpy or networkx) can be used.