Một người dân Bắc Ninh đang ở xã A và cần chuyển hàng hóa gấp tới địa chỉ ở 4 xã B, C, D, E trong tỉnh. Người này thuê xe ô tô để đi và xuất phát từ xã A

18/22

Một người dân Bắc Ninh đang ở xã A và cần chuyển hàng hóa gấp tới địa chỉ ở 4 xã B, C, D, E trong tỉnh. Người này thuê xe ô tô để đi và xuất phát từ xã A lần lượt đi qua các xã còn lại (mỗi xã đi qua một lần duy nhất) rồi quay trở về xã ban đầu với thời gian (đơn vị: phút) đi giữa các xã cho như hình vẽ. Biết giá thuê xe theo thỏa thuận là 750000 đồng/giờ và không thay đổi khi đi. Chi phí tiền thuê xe thấp nhất bao nhiêu nghìn đồng để người này xong công việc của mình? Một người dân Bắc Ninh đang ở xã A và cần chuyển hàng hóa gấp tới địa chỉ ở 4 xã B, C, D, E trong tỉnh. Người này thuê xe ô tô để đi và xuất phát từ xã A (ảnh 1)

Giải thích

Lời giải

Đáp án:\[700\]

Dựa vào thuật toán láng giềng gần nhât, ta xét các chu trình sau:

\[\begin{array}{*{20}{l}}{AEDCBA:{\rm{ }}8 + 9 + 10 + 12 + 17 = 56}\\{BCDEAB:{\rm{ }}12 + 10 + 9 + 8 + 17 = 56}\\{CDEABC:{\rm{ }}10 + 9 + 8 + 17 + 12 = 56}\\{DEABCD:{\rm{ }}9 + 8 + 17 + 12 + 10 = 56}\\{EABCDE:{\rm{ }}8 + 17 + 12 + 10 + 9 = 56}\end{array}\]

Như vậy chu trình có tổng số phút ít nhất là \(56\) phút, do đó chi phí thuê xe thấp nhất là:

\(\frac{{56}}{{60}}.750 = 700.\) (nghìn đồng).