Hằng năm, trường THPT M tổ chức các đoàn đi thăm hỏi và chúc Tết tứ

Câu hỏi số 950815:

Vận dụng

Hằng năm, trường THPT M tổ chức các đoàn đi thăm hỏi và chúc Tết tứ thân phụ mẫu cao tuổi của cán bộ, giáo viên và nhân viên trong trường. Đoàn số 1 có nhiệm vụ đến thăm 4 gia đình tại các địa điểm A, B, C, D. Đoàn xuất phát từ trường THPT M, đến thăm đủ 4 gia đình (mỗi gia đình đúng một lần). Sau khi thăm xong gia đình cuối cùng, đoàn kết thúc hành trình tại đó (không quay về trường). Do điều kiện giao thông dịp cuối năm, đoạn đường AB chỉ có thể đi theo chiều từ A đến B, không đi được theo chiều ngược lại (hình vẽ). Đoàn số 1 đã chọn được lộ trình di chuyển có tổng quãng đường di chuyển ngắn nhất. Tổng quãng đường ngắn nhất đó dài bao nhiêu km?

Trả lời:

Đáp án đúng là:

Quảng cáo

Xem lời giải

Câu hỏi:950815

Phương pháp giải

Áp dụng thuật toán Dijkstra.

Giải chi tiết

Gán nhãn cho điểm xuất phát $l(M) = 0$ và coi đây là nhãn vĩnh viễn.

Các đỉnh A, B, C, D lúc này có nhãn tạm thời dựa trên khoảng cách từ M:

$l(A) = 8$, $l(B) = 6$, $l(C) = 4$, $l(D) = 7$.

So sánh các nhãn tạm thời, ta thấy $l(C) = 4$ là nhỏ nhất,. Ta chọn C làm điểm tiếp theo của hành trình.

Từ C, ta xem xét các gia đình chưa thăm (A, B, D).

- Khoảng cách đến A là $l(C) + AC = 4 + 6 = 10$.

- Khoảng cách đến B là $l(C) + CB = 4 + 3 = 7$.

- Khoảng cách đến D là $l(C) + CD = 4 + 5 = 9$.

Thấy hiện tại nhãn nhỏ nhất từ các lựa chọn là $l(B) = 7$. Ta chọn B là điểm tiếp theo.

Từ B, ta còn A và D. Do tuyến đường từ B đến A bị chặn, nên đi đến D trước, rồi tới A:

$l(B) + BD + DA = 7 + 4 + 5 = 16$.

Đáp án cần điền là: 16

Group 2K8 ôn Thi ĐGNL & ĐGTD Miễn Phí

Câu hỏi trước Câu tiếp theo

>> 2K9 Chú ý! Lộ Trình Sun 2027 - 1 lộ trình ôn đa kỳ thi (TN THPT, ĐGNL (Hà Nội/ Hồ Chí Minh), ĐGNL Sư Phạm, ĐGTD, ĐGNL Bộ Công an, ĐGNL Bộ Quốc phòngTD - Click xem ngay) tại Tuyensinh247.com. Cập nhật bám sát bộ SGK mới, Thầy Cô giáo giỏi, 3 bước chi tiết: Nền tảng lớp 12; Luyện thi chuyên sâu; Luyện đề đủ dạng đáp ứng mọi kì thi.