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?

(AI giải đề cho tôi)
Từ hình vẽ, các cạnh và thời gian (phút): $AB=17$, $AE=8$, $AD=20$, $BE=29$, $BC=12$, $CE=19$, $CD=10$, $ED=9$. Lưu ý không có cạnh nối trực tiếp $A$ với $C$. Cần tìm chu trình Hamilton xuất phát từ $A$, qua $B,C,D,E$ mỗi xã đúng một lần rồi về $A$ với tổng thời gian nhỏ nhất. Xét các chu trình khả dĩ (không dùng cạnh $AC$ vì không tồn tại):
- $A\to B\to C\to D\to E\to A$: $17+12+10+9+8=56$;
- $A\to B\to C\to E\to D\to A$: $17+12+19+9+20=77$;
- $A\to B\to D\to C\to E\to A$: $17+10+10+19+8=64$;
- $A\to B\to D\to E\to C\to A$: $17+10+9+19+12=67$;
- $A\to B\to E\to C\to D\to A$: $17+29+19+10+20=95$;
- $A\to B\to E\to D\to C\to A$: $17+29+9+10+12=77$;
- $A\to D\to B\to C\to E\to A$: $20+10+12+19+8=69$;
- $A\to D\to B\to E\to C\to A$: $20+10+29+19+12=90$;
- $A\to D\to C\to B\to E\to A$: $20+10+12+29+8=79$;
- $A\to D\to E\to B\to C\to A$: $20+9+29+12+12=82$;
- $A\to D\to E\to C\to B\to A$: $20+9+19+12+17=77$;
- $A\to E\to B\to C\to D\to A$: $8+29+12+10+20=79$.

Chu trình ngắn nhất là $A\to B\to C\to D\to E\to A$ với tổng thời gian $56$ phút $=\frac{56}{60}$ giờ. Chi phí thuê xe thấp nhất: $750000\times \frac{56}{60}=700000$ đồng $=700$ nghìn đồng. Kết quả khớp với đáp án nguồn ($700$).