wip

76. Interplanetary Pathfinder

Time Limit: 1 seconds

Memory Limit: 1024 MB

Rating: 1200

You are given a single string, containing the $x$ and $y$ coordinates of $n$ planets. Find the shortest path between the planets, given that you visit all planets, and you only visit a single planet once. Find the shortest distance travelled, and the order in which you visit the planets. Represent the order as the index value the coordinates would have if they were all added to a list. The starting planet is always the first coordinates given.

A string of numbers, where the $x$ and $y$ coordinates of a single planet are divided by a space. The coordinates of each planet are also divided by a space. eg: $4 \quad 3 \quad 5 \quad 6 \quad 7 \quad 8$ translates to: Planet 1: $(4,3)$ Planet 2: $(5,6)$ Planet 3: $(7,8)$ The length of the input does not exceed $10^3$.

Give the outputs on separate lines, in the given order. The shortest distance to travel between all planets, to 2 decimal places. The indexes of the planets in the order they were visited. The index always starts with $0$.

Sample Input 0:
0 0 0 2 2 0

Sample Output 0:
4.83
0 1 2

The input can be divided and placed into a 2d array, [[0,0],[0,2],[2,0]] The shortest path between all the points is $4.83$ units long. The order the points are visited is 0 ([0,0]), 1 ([0,2]), and 2 ([2,0]).

KL Coding Cup October 2024 > Problem 14