Problem Statement
Travelling Salesman Problem: Given a set of cities and distance between every pair of cities, find the shortest possible route that visits every city exactly once and returns to the starting point.
Specifications
• Input: Your script should read from stdin in the following format.
– First line will contain either euclidean or non euclidean indicating whether the distances between the cities are Euclidean or not.
– Second line will contain the number of cities (N). E.g. 100 (Indices 0 - 99)
– Next N lines will contain the two-dimensional coordinates (space separated) of the cities.
– Next N lines will contain N space separated distances: distance of the nth city from each city in the order.
– All coordinates and distances will be floating point numbers.
• Output: The output should be tours (one tour/line) as space separated indices of cities. Do not write the origin city’s index in the end again. Invalid tours will be considered as no tours at all.
