AMC 8 2024 Problem 14
AMC8 2024 年第 14 题
基本计数原理★★★☆☆
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?
如图所示，A、M、C、X、Y、Z几座小镇之间通过单行道相连。图中标明了每条单行道的长度，单位为千米。请问沿单行道从A行驶到Z的最短距离为多少千米？（图形未按比例绘制）
- A.28
- B.29
- C.30
- D.31
- E.32
正确答案 · Correct Answer
A
解析 · Solution
解法1
我们可以简单地看到路径 将给出最小值。相加得 5+2+6+5+10 = 28 。这很好，因为它也是最小值，巩固了我们的答案。你也可以简单地暴力破解或事先思考，例如，从 A 到 M 可以有 2 种方式； (5+2) 或 ，所以你应该选择较短的路线 (5+2)。另一个例子是 M 到 C，两种方式是 6+5 和另一种是 14。选择较短的路线。在此之后，你需要再考虑几次，5+10 () 是否大于 17 ()，事实并非如此，并考虑 25 () 是否大于 14+10 () 或 6+5+10 ()，事实也并非如此。TLDR: 5+2+6+5+10 = 28 。[注：这可能只是解法背后的思考。]{双重注：正如 MaxyMoosy 所说，因为这个答案是最小的，所以它一定是正确答案。}
我们可以执行 Dijkstra 算法来找出从 到包括 在内的每个其他城镇的最短路径。这有效地证明了，假设我们正确执行算法，我们将找到最短距离。算法每一步的距离估计（从 到每个节点）如下所示：
$\begin{array}{|c|c|c|c|c|c|c|}
\hline 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}
$
步骤如下：从初始节点 $$ 开始，设置 $d(A)=0$，并且对于所有 $$ 设置 $$，其中 $$ 表示从 $$ 到 $$ 的距离。考虑出边 $(A,X)$ 和 $(A,M)$，并更新距离估计 $d(X)=5$ 和 $d(M)=8$，完成表格的第一行。节点 $$ 是未访问节点中距离估计最小的节点，因此我们将考虑 $$ 及其出边 $(X,Y)$ 和 $(X,M)$。距离估计 $$ 等于 $d(X)+10=15$，并且距离估计 $$ 更新为 $d(X)+2=7$，因为 $7 < 8$。这完成了表格的第二行。对每个未访问节点（按距离估计顺序）重复此过程，一旦算法完成，就能得到正确的距离 $d(Z) = 28$。从 出发，我们想要找到到 的最短路线，因此我们尝试找到通过每个节点（不一定全部）的最短路径。我们应该沿着箭头走，因为它们都通向 。从 出发，我们可以走 2 条路径，到 (8) 或到 (5)。我们走到 ，因为 5 < 8。从 出发，我们走到 (2 < 10)，我们走到 (6 < 14 < 25)，我们走到 (5 < 17)，最后走到 。相加得 5 + 2 + 6 + 5 + 10 = 28 = 。
我们可以划掉一些路线：AM 可以划掉，因为 AXM 更短；XY 可以划掉，因为 XMY 更短；YZ 可以划掉，因为 YCZ 更短；MC 可以划掉，因为 MYC 更短；MZ 可以划掉，因为 MCZ 更短。最后，我们剩下一条从 A 到 Z 的路径 AXMYCZ，相加得 28 =.
Solution 1
We can simply see that path will give us the smallest value. Adding, 5+2+6+5+10 = 28. This is nice as it's also the smallest value, solidifying our answer. You can also simply brute it or sort of think ahead example, getting from A to M can be done 2 ways; ( 5+2 ) or , so you should take the shorter route ( 5+2 ). Another example is M to C, two ways is 6+5 and the other is 14. Take the shorter route. After this, you need to consider a few more times if 5+10 ( ) is greater than ), which it is not, and consider if ) is greater than 14+10 ( ) or 6+5+10 ( ) which it is not. TLDR: 5+2+6+5+10 = 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.} We can execute Dijkstra's algorithm to find the shortest path from to every other town, including . 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 to each node) are shown below:
$\begin{array}{|c|c|c|c|c|c|c|} \hline 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 $$, set $d(A)=0$ and $$ for all $$ where $$ indicates the distance from $$ to $$. 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 $$ is the unvisited node with the lowest distance estimate, so we will consider $$ and its outgoing edges $(X,Y)$ and $(X,M)$. The distance estimate $$ equals $d(X)+10=15$, and the distance estimate $$ 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) = 28$ once the algorithm is complete. From $$, we want to find the shortest route to $$, so we want to try to find the shortest path through each node (not necessarily all of them). We should follow the arrows, since all of them lead to $$. From $$, there are 2 paths we can take, to $$ (8), or to $$ (5). We travel to $$, since $5 < 8$. From $$, we go to $$ $(2 < 10)$, we go to $$ $(6 < 14 < 25)$, we go to $$, $(5 < 17)$ and finally go to $$. Adding up gives $5 + 2 + 6 + 5 + 10 = 28$. We can cross off a few routes: AM can be crossed off because AXM is shorter XY can be crossed off because XMY is shorter YZ can be crossed off because YCZ is shorter MC can be crossed off because MYC is shorter MZ can be crossed off because MCZ is shorter Finally, we are left with a single path AXMYCZ from A to Z which adding it up gives $28$.继续练习