3D path - MarisaOJ: Marisa Online Judge

Given a cube

$A$ of size

$n \times n \times n$ . On cell

$(x, y, z)$ written an integer

$A_{x, y, z}$ . From

$(x, y, z)$ , you can reach

$(x', y', z')$ if

$|x-x'|+|y-y'|+|z-z'|=1$ . You are currently standing at

$(1, 1, 1)$ . Find the shortest cost to reach

$(n, n, n)$ knowing that moving to cell

$(i, j, k)$ costs you

$A_{i, j, k}$ . ### Input - The first line contains an integer

$n$ . - The next

$n \times n$ lines, the

$i^{th}$ line contains

$n$ integers

$A_{\lfloor \frac{i - 1}{n} + 1 \rfloor, (i - 1) \mod n + 1, k}$ . In other words, the first group of

$n$ lines is the matrix

$A_{1, j, k}$ , the second group of

$n$ lines is the matrix

$A_{2, j, k}$ and so on... ### Output - Print the weight of the shortest path from

$(1, 1, 1)$ to

$(n, n, n)$ . ### Constraints -

$1 \le n \le 100$ . -

$1 \le A_{i, j, k} \le 1000$ . ### Example Input:

$2 1 2 3 1 3 3 1 2$

Output:

$5$

#### Note: - Moving from

$(1, 1, 1)$ to

$(1, 1, 2)$ cost

$2$ . - Moving from

$(1, 1, 2)$ to

$(1, 2, 2)$ cost

$1$ . - Moving from

$(1, 2, 2)$ to

$(2, 2, 2)$ cost

$2$ .

Topic

Graph

Shortest path

Rating

1100

Solution (0)

Solution