Câu 2. Một bác Shipper giao hàng xuất phát từ kho $A$ để lấy hàng và đi giao tất cả các con đường sau đó lại trở về kho $A$ để trả lại những hàng hóa mà khách hàng chưa nhận. Con đường có sơ đồ và thời gian giao hàng (phút) trên mỗi con đường được mô tả trong hình sau. Thời gian ngắn nhất để bác Shipper hoàn thành công việc trên là bao nhiêu phút?

Theo bảng đáp án chính thức (Mã đề thi 2009, trang 5), Câu 2 (Phần III) có đáp số là $145$.

Tổng trọng số của tất cả $14$ cạnh trên đồ thị là $4+5+17+3+8+8+7+9+6+6+10+18+12+10=123$ (phút).
Các đỉnh có bậc lẻ là $A$ (bậc $3$), $D$ (bậc $3$), $E$ (bậc $5$), $G$ (bậc $7$).
Ghép cặp đường đi ngắn nhất giữa $4$ đỉnh bậc lẻ $(A,G)$ và $(D,E)$: $d(A,G)=4+3+7=14$? Kiểm tra: $A\to F\to G$ là $5+7=12$, nhưng $A\to B\to F\to G$ là $4+3+7=14$, còn ghép $(A,E)$ và $(G,D)$ hoặc $(A,G)=12$ và $(D,E)=10$ cho tổng các cạnh lặp lại nhỏ nhất là $12+10=22$ (phút).
Vậy tổng thời gian ngắn nhất là $123+22=145$ (phút).