Một trò chơi điện tử quy định như sau: Có 6 trụ $A,B,C,D,E,F$ với số lượng các thử thách

Câu hỏi số 790141:

Vận dụng

Một trò chơi điện tử quy định như sau: Có 6 trụ $A,B,C,D,E,F$ với số lượng các thử thách trên đường đi giữa các cặp trụ được mô tả trong hình bên. Người chơi xuất phát từ trụ A , đi qua các trụ đến D , mỗi khi đi qua một trụ thỉ trụ đó sẽ bị phá hủy và không thể quay trở lại trụ đó được nữa. Tổng số thử thách của đường đi thoả mãn điểu kiện trên nhận giá trị nhỏ nhất là bao nhiêu?

Trả lời:

Đáp án đúng là:

Quảng cáo

Xem lời giải

Câu hỏi:790141

Phương pháp giải

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

Giải chi tiết

Áp dụng thuật toán Dijkstra, ta có:

Đầu tiên, ta gắn nhãn đỉnh A là $I(A) = 0$ và gắn cho ba đỉnh kề với A là $B,F$ và D các nhãn tạm thời $I(A) + 4,I(A) + 3$ và $I(A) + 20$. Chọn số nhỏ nhất trong chúng và viết $I(F) = 3$. Đỉnh F bây giờ được gắn nhãn vĩnh viễn là 3.

Tiếp theo, ta gắn cho các đinh kề với F là $B,C$ và E các nhãn tạm thời $I(F) + 6,I(F) + 5$ và $I(F)$ +15 (B hiện có hai nhãn tạm thời là 4 và 9). Nhãn tạm thời nhỏ nhất trong các nhãn đã gán (ờ $B,C,E)$ hiện nay là 4 (tại B$)$, nên ta viết $I(B) = 4$. Đỉnh B được gắn nhãn vĩnh viễn là 4.

Bây giờ ta xét các đĩnh kề với B (mà chưa được gắn nhãn vĩnh viễn) là C và E. Ta gắn cho đỉnh C nhãn tạm thời là $I(B) + 11$ (hiện C có hai nhãn tạm thời là 8 và 15), gắn cho đỉnh E nhãn tạm thời là $I(B) + 9$ (E hiện có hai nhãn tạm thời là 18 và 13). Nhãn tạm thời nhỏ nhất bây giờ là 8 (tại C), do đó ta viết $I(C) = 8$.

Bây giờ ta xét các đỉnh kề với C (mà chưa được gắn nhãn vĩnh viễn) là E và $\text{~D}$. Ta gắn nhãn cho đỉnh E tạm thời là $I(C) + 2$ (hiện E có ba nhãn tạm thời là 18,13 và 10), gắn cho đỉnh D nhãn tạm thời là $I(C) + 10$. Nhãn tạm thời nhỏ nhất bây giờ là 10 (tại E), do đó ta viết $I(E) = 10$

Xét đỉnh kề với E là D , ta gắn cho D nhãn tạm thời $I(E) + 7$ (hiện D có hai nhãn tạm thời là 18 và 17). Vậy đỉnh D sẽ được gắn nhãn vĩnh viễn là 17 hay $I(D) = 17$.

Vì $I(D) = 17$ nên đường đi ngắn nhất từ A đến D có độ dài là 17. Đường đi đó là: AFCED.

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

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

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

>> 2K8 Chú ý! Lộ Trình Sun 2026 - 3IN1 - 1 lộ trình ôn 3 kì thi (Luyện thi 26+ TN THPT, 90+ ĐGNL HN, 900+ ĐGNL HCM, 70+ ĐGTD - Click xem ngay) tại Tuyensinh247.com.Đầy đủ theo 3 đầu sách, Thầy Cô giáo giỏi, luyện thi theo 3 giai đoạn: Nền tảng lớp 12, Luyện thi chuyên sâu, Luyện đề đủ dạng đáp ứng mọi kì thi.