Problem E
Travelling Salesperson 2D
Input
Your program should take as input a single TSP instance. It will be run several times, once for every test case. The time limit is per test case.
The first line of standard input contains an integer
The distance between two points is computed as the Euclidean distance between the two points, rounded to the nearest integer.
Output
Standard output should consist of
Score
Let
The score on a test case is
The algorithm giving the value
GreedyTour tour[0] = 0 used[0] = true for i = 1 to n-1 best = -1 for j = 0 to n-1 if not used[j] and (best = -1 or dist(tour[i-1],j) < dist(tour[i-1],best)) best = j tour[i] = best used[best] = true return tour
The sample output gives the tour found by GreedyTour on the sample input. The length of the tour is 323.
Sample Input 1 | Sample Output 1 |
---|---|
10 95.0129 61.5432 23.1139 79.1937 60.6843 92.1813 48.5982 73.8207 89.1299 17.6266 76.2097 40.5706 45.6468 93.5470 1.8504 91.6904 82.1407 41.0270 44.4703 89.3650 |
0 8 5 4 3 9 6 2 1 7 |