Từ kho D xe bưu chính đến lấy thư từ các hộp thư tại E,F,G và H rồi quay lại kho. Sơ đồ bên dưới hiển thị thời gian xe bưu chính di chuyển giữa các hộp thư (đơn vị: phút),

Thời gian ngắn nhất để xe bưu chính thực hiện điều đó là bao nhiêu phút?

Đáp án: $35$ phút 

Giải thích các bước giải:

Gọi thời gian thỏa mãn đề là $t=0$

+ Từ $D$ chọn quãng đường $DH$ có thời gian đi ngắn nhất

$\to t=3$ phút

Đường đi lúc này là $DH$

+ Từ $H$ chọn quãng đường $HG$ có thời gian đi ngắn nhất

$\to t=3+6=9$ phút

Đường đi lúc này là $DHG$

+ Từ $G$ chọn quãng đường $GE$ có thời gian đi ngắn nhất

$\to t=9+10=19$ phút

Đường đi lúc này là $DHGE$

+ Còn mỗi địa điểm $F$ chưa thăm nên ta chọn quãng đường $EF$ và trở về $D$

$\to t=19+7+9=35$ phút

Đường đi là $DHGEFD$