The attached figure is an undirected graph. The circled numbers represent the nodes, and the numbers along the edges are their lengths (symmetrical in both directions). An Alibaba Hema Xiansheng carrier starts at point A and will pick up three orders from merchants B_{1}, B_{2}, B_{3} and deliver them to three customers C_{1}, C_{2}, C_{3}, respectively. The carrier drives a scooter with a trunk that holds at most two orders at any time. All the orders have equal size. Find the shortest travel route that starts at A and ends at the last delivery. To simplify this question, assume no waiting time during each pickup and delivery.
Solution
The shortest travel distance is 16, attained by the carrier taking the following stops: A \rightsquigarrow B_{2} \rightsquigarrow C_{2} \rightsquigarrow B_{1} \rightsquigarrow B_{3} \rightsquigarrow C_{3} \rightsquigarrow C_{1}. There are two slightly different routes with the same length of 16: Route 1: 2(A) \rightarrow 6 \rightarrow 7(B_{2}) \rightarrow 8 \rightarrow 11(C_{2}) \rightarrow 8 \rightarrow 3(B_{1}) \rightarrow 4(B_{3}) \rightarrow 15 \rightarrow 14 \rightarrow 13(C_{3}) \rightarrow 12(C_{1}). Route 2: 2(A) \rightarrow 6 \rightarrow 7(B_{2}) \rightarrow 10 \rightarrow 11(C_{2}) \rightarrow 8 \rightarrow 3(B_{1}) \rightarrow 4(B_{3}) \rightarrow 15 \rightarrow 14 \rightarrow 13(C_{3}) \rightarrow 12(C_{1}).
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.