174. Interstellar Travel

Codeforces

IDCF10269174

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

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. You 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. Recall that to calculate the distance between two points in 3D space, you can use the distance formula: The 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). Output 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. ## Input The 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). ## Output Output 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. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $, $ n \leq 8 $, be the number of planets. Let $ 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. Let $ E = (0, 0, 0) $ be the Earth's position. The Euclidean distance between two points $ a = (a_x, a_y, a_z) $ and $ b = (b_x, b_y, b_z) $ is: $$ d(a, b) = \sqrt{(a_x - b_x)^2 + (a_y - b_y)^2 + (a_z - b_z)^2} $$ **Constraints** 1. $ 1 \leq n \leq 8 $ 2. All coordinates are integers. **Objective** Find the minimum total distance of a closed path starting and ending at $ E $, visiting each planet in $ P $ exactly once: $$ \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) $$ where $ S_n $ is the set of all permutations of $ \{1, 2, \dots, n\} $.

API Response (JSON)

{
  "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 r...",
      "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 coo...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments