{"problem":{"name":"174. Interstellar Travel","description":{"content":"You're traveling through space, but unfortunately, your spaceship has a limited amount of fuel. There are $n$ planets that you want to travel to on your journey through space, and each planet can be r","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10269174"},"statements":[{"statement_type":"Markdown","content":"You're traveling through space, but unfortunately, your spaceship has a limited amount of fuel. There are $n$ planets that you want to travel to on your journey through space, and each planet can be represented by an $x$, $y$, and $z$ coordinate. \n\nYou start on Earth, which can be represented as the origin (0, 0, 0) on the 3D coordinate plane. You want to find the minimum distance you can travel, if you start on Earth, visit all of the planets at least once, and end on Earth.\n\nRecall that to calculate the distance between two points in 3D space, you can use the distance formula:\n\nThe first line of input consists of a single positive integer $n$: the number of planets. $n$ will be less than or equal to 8.\n\nThe next $n$ lines each contain three space-separated integers: the $x$, $y$, and $z$ coordinates of each planet.\n\nRemember that the coordinates of the Earth are (0, 0, 0).\n\nOutput a single positive integer: the minimum total distance that you travel, if you start and end on Earth, and visit all of the planets.\n\nDon't round your answer.\n\n## Input\n\nThe first line of input consists of a single positive integer $n$: the number of planets. $n$ will be less than or equal to 8.The next $n$ lines each contain three space-separated integers: the $x$, $y$, and $z$ coordinates of each planet.Remember that the coordinates of the Earth are (0, 0, 0).\n\n## Output\n\nOutput a single positive integer: the minimum total distance that you travel, if you start and end on Earth, and visit all of the planets.Don't round your answer.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ n \\leq 8 $, be the number of planets.  \nLet $ P = \\{p_1, p_2, \\dots, p_n\\} $, where $ p_i = (x_i, y_i, z_i) \\in \\mathbb{Z}^3 $, be the set of planet coordinates.  \nLet $ E = (0, 0, 0) $ be the Earth's position.  \n\nThe Euclidean distance between two points $ a = (a_x, a_y, a_z) $ and $ b = (b_x, b_y, b_z) $ is:  \n$$\nd(a, b) = \\sqrt{(a_x - b_x)^2 + (a_y - b_y)^2 + (a_z - b_z)^2}\n$$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 8 $  \n2. All coordinates are integers.  \n\n**Objective**  \nFind the minimum total distance of a closed path starting and ending at $ E $, visiting each planet in $ P $ exactly once:  \n$$\n\\min_{\\sigma \\in S_n} \\left( d(E, p_{\\sigma(1)}) + \\sum_{i=1}^{n-1} d(p_{\\sigma(i)}, p_{\\sigma(i+1)}) + d(p_{\\sigma(n)}, E) \\right)\n$$  \nwhere $ S_n $ is the set of all permutations of $ \\{1, 2, \\dots, n\\} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10269174","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}