2024 AMC 8 Problems/Problem 14

1 Problem
2 Solution 1
3 Solution 2 (Advanced)
4 Video Solution 1 (easy to digest) by Power Solve
5 Video Solution 2 by SpreadTheMathLove
6 Video Solution 3 by NiuniuMaths (Easy to understand!)
7 Video Solution by CosineMethod [🔥Fast and Easy🔥]
8 Video Solution by Math-X (First fully understand the problem!!!)
9 See Also

Problem

The one-way routes connecting towns $A,M,C,X,Y,$ and $Z$ are shown in the figure below(not drawn to scale).The distances in kilometers along each route are marked. Traveling along these routes, what is the shortest distance from A to Z in kilometers?

$\textbf{(A)}\ 28 \qquad \textbf{(B)}\ 29 \qquad \textbf{(C)}\ 30 \qquad \textbf{(D)}\ 31 \qquad \textbf{(E)}\ 32$

Solution 1

We can simply see that path $A \rightarrow X \rightarrow M \rightarrow Y \rightarrow C \rightarrow Z$ will give us the smallest value. Adding, $5+2+6+5+10 = \boxed{28}$ . This is nice as it’s also the smallest value, solidifying our answer.

You can also simply brute-force it or sort of think ahead - for example, getting from A to M can be done $2$ ways; $A \rightarrow X \rightarrow M$ ( $5+2$ ) or $A \rightarrow M (8)$ , so you should take the shorter route ( $5+2$ ). Another example is M to C, two ways - one is $6+5$ and the other is $14$ . Take the shorter route. After this, you need to consider a few more times - consider if $5+10$ ( $Y \rightarrow C \rightarrow Z$ ) is greater than $17 (Y \rightarrow Z$ ), which it is not, and consider if $25 (M \rightarrow Z$ ) is greater than $14+10$ ( $M \rightarrow C \rightarrow Z$ ) or $6+5+10$ ( $M \rightarrow Y \rightarrow C \rightarrow Z$ ) which it is not. TL;DR: $5+2=6=5=10 = \boxed{28}$ . [Note: This is probably just the thinking behind the solution.] {Double-note: As MaxyMoosy said, since this answer is the smallest one, it has to be the right answer.}

~MaxyMoosy ~HACKER2022

Solution 2 (Advanced)

We can execute Dijkstra's algorithm by hand to find the shortest path from $A$ to every other town, including $Z$ . This effectively proves that, assuming we execute the algorithm correctly, that we will have found the shortest distance. The distance estimates for each step of the algorithm (from $A$ to each node) are shown below:

$\begin{array}{|c|c|c|c|c|c|c|} \hline \text{Current node} & A & M & C & X & Y & Z \\ \hline A & 0 & 8 & \infty & 5 & \infty & \infty \\ X & 0 & 7 & \infty & 5 & 15 & \infty \\ M & 0 & 7 & 21 & 5 & 13 & 32 \\ Y & 0 & 7 & 18 & 5 & 13 & 30 \\ C & 0 & 7 & 18 & 5 & 13 & 28 \\ Z & 0 & 7 & 18 & 5 & 13 & \textbf{28} \\ \hline \end{array}$ The steps are as follows: starting with the initial node $A$ , set $d(A)=0$ and $d(v)=\infty$ for all $v \in \{M,C,X,Y,Z\}$ where $d(v)$ indicates the distance from $A$ to $v$ . Consider the outgoing edges $(A,X)$ and $(A,M)$ and update the distance estimates $d(X)=5$ and $d(M)=8$ , completing the first row of the table.

The node $X$ is the unvisited node with the lowest distance estimate, so we will consider $X$ and its outgoing edges $(X,Y)$ and $(X,M)$ . The distance estimate $d(Y)$ equals $d(X)+10=15$ , and the distance estimate $d(M)$ updates to $d(X)+2=7$ , because $7 < 8$ . This completes the second row of the table. Repeating this process for each unvisited node (in order of its distance estimate) yields the correct distance $d(Z) = \boxed{\textbf{(A) } 28}$ once the algorithm is complete.

~scrabbler94

Video Solution 1 (easy to digest) by Power Solve

https://youtu.be/2AVrraozwF8

Video Solution 2 by SpreadTheMathLove

https://www.youtube.com/watch?v=RRTxlduaDs8

Video Solution 3 by NiuniuMaths (Easy to understand!)

https://www.youtube.com/watch?v=V-xN8Njd_Lc

~NiuniuMaths

Video Solution by CosineMethod [🔥Fast and Easy🔥]

https://www.youtube.com/watch?v=bAxLRYT6SCw

Video Solution by Math-X (First fully understand the problem!!!)

https://youtu.be/BaE00H2SHQM?si=y_YVZFC4DQdB2qhM&t=3280

~Math-X

2024 AMC 8 (Problems • Answer Key • Resources)
Preceded by Problem 13	Followed by Problem 15
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AJHSME/AMC 8 Problems and Solutions

Page

Toolbox

Search