Problem 14 · 2024 AMC 8
Hard
Logic & Word Problems
work-backwardcasework
Show answer
Answer: A — 28 km.
Show hints
Hint 1 of 2
Don't try to trace whole routes — too many. Instead label each town with its OWN shortest distance from A, in the order the towns can be reached.
Still stuck? Show hint 2 →
Hint 2 of 2
Technique (shortest-path relaxation): a town's best distance = the smallest "(best distance to a town that feeds it) + (that edge)". Solve them in flow order A, X, M, Y, C, Z.
Show solution
Approach: shortest-path table, town by town
- Rather than list every full route, find the shortest distance to each town from A, building up in the order towns become reachable. Each town's value = the cheapest "(arrived-distance to a feeder) + (its edge to here)." Start: A→X = 5 (only way in).
- A→M = min(8 direct, 5 + 2 via X) = 7. Going through X beats the direct road.
- A→Y = min(5 + 10 via X, 7 + 6 via M) = 13.
- A→C = min(7 + 14 via M, 13 + 5 via Y) = 18.
- A→Z = min(7 + 25 via M, 13 + 17 via Y, 18 + 10 via C) = 28 (via C). This transfers: this is Dijkstra's idea — once a town has its final shortest label, every later town can lean on it, so you never re-explore whole paths.
Mark:
· log in to save