Trong một trò chơi, người chơi muốn tìm đường đi ngắn nhất để đi từ A đến P, biết từ A đến P có những đường đi như hình vẽ và khoảng cách giữa các vị trí được cho trên hình. Đường đi thoả mãn điều kiện trên nhận giá trị nhỏ nhất là bao nhiêu?
Quảng cáo
Trả lời:
Giải bởi Vietjack
Đáp án:
21
Đáp án: 21
Cách 1: Liệt kê
Bảng liệt kê các lộ trình từ A đến P
|
Lộ trình di chuyển |
Chi tiết các đoạn đường |
Tổng quãng đường |
|
\(A \to B \to N \to P\) |
\(8 + 9 + 10\) |
27 |
|
\(A \to B \to M \to P\) |
\(8 + 8 + 6\) |
22 |
|
\(A \to B \to M \to N \to P\) |
\(8 + 8 + 6 + 10\) |
32 |
|
\(A \to C \to B \to N \to P\) |
\(7 + 7 + 9 + 10\) |
33 |
|
\(A \to C \to M \to P\) |
\(7 + 8 + 6\) |
21 |
|
\(A \to C \to M \to N \to P\) |
\(7 + 8 + 6 + 10\) |
31 |
Dựa vào bảng trên, học sinh có thể thấy ngay lộ trình qua các điểm \(A \to C \to M \to P\) là con đường ngắn nhất với tổng giá trị là 21.
Cách 2: Thuật toán Dijkstra
Quy ước: Điểm B có nhãn có dạng [d, A], trong đó d là khoảng cách ngắn nhất từ A đến điểm B.
Diễn giải thuật toán
Bước 1: Chọn đỉnh A làm vĩnh viễn
Từ A, ta cập nhật nhãn tạm thời cho các đỉnh kề nó là B và C.
B có nhãn [8, A] và C có nhãn [7, A].
Vì \(7 < 8\), ta chọn đỉnh C để cố định nhãn vĩnh viễn.
Bước 2: Từ đỉnh vĩnh viễn C
Xét các đỉnh kề C chưa có nhãn vĩnh viễn là B và M.
Đến B qua C: \(7 + 7 = 14\) (lớn hơn nhãn cũ là 8 nên không cập nhật).
Đến M qua C: \(7 + 8 = 15\). Ta có nhãn tạm thời cho M là [15, C].
Trong các nhãn tạm thời (B: 8, M: 15), số 8 là nhỏ nhất, ta chọn B làm đỉnh vĩnh viễn tiếp theo.
Bước 3: Từ đỉnh vĩnh viễn B
Xét các đỉnh kề B chưa có nhãn vĩnh viễn là N và M.
Đến N qua B: \(8 + 9 = 17\). Nhãn tạm thời cho N là [17, B].
Đến M qua B: \(8 + 8 = 16\) (lớn hơn nhãn cũ là 15 nên không cập nhật).
Trong các nhãn tạm thời (N: 17, M: 15), số 15 là nhỏ nhất, ta chọn M làm đỉnh vĩnh viễn.
Bước 4: Từ đỉnh vĩnh viễn M
Xét các đỉnh kề M chưa có nhãn vĩnh viễn là N và P.
Đến N qua M: \(15 + 6 = 21\) (lớn hơn nhãn cũ là 17 nên không cập nhật).
Đến P qua M: \(15 + 6 = 21\). Nhãn tạm thời cho P là [21, M].
So sánh các nhãn tạm thời còn lại (N: 17, P: 21), ta chọn N làm đỉnh vĩnh viễn.
Bước 5: Từ đỉnh vĩnh viễn N
Đến P qua N: \(17 + 10 = 27\) (lớn hơn nhãn cũ là 21 nên không cập nhật).
Cuối cùng, đỉnh P nhận nhãn vĩnh viễn là [21, M].
Kết luận:
Đường đi ngắn nhất có độ dài là 21.
Truy ngược từ nhãn: \(P \leftarrow M \leftarrow C \leftarrow A\).
Lộ trình: A → C → M → P.
Đáp án: 21
Hot: 1000+ Đề thi giữa kì 2 file word cấu trúc mới 2026 Toán, Văn, Anh... lớp 1-12 (chỉ từ 60k). Tải ngay
Sách thầy cô Vietjack biên soạn:
- 20 đề thi tốt nghiệp môn Toán (có đáp án chi tiết) ( 38.500₫ )
- 20 Bộ đề, Tổng ôn, sổ tay môn Toán (có đáp án chi tiết) ( 55.000₫ )
- Bộ đề thi tốt nghiệp 2025 các môn Toán, Lí, Hóa, Văn, Anh, Sinh, Sử, Địa, KTPL (có đáp án chi tiết) ( 36.000₫ )
- Tổng ôn lớp 12 môn Toán, Lí, Hóa, Văn, Anh, Sinh Sử, Địa, KTPL (Form 2025) ( 36.000₫ )
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
Đáp án: 1200
Với \(x\) mét lưới (\(1 \le x \le 18\)) bán ra , ta có
Hàm chi phí \(C(x) = {x^3} - 3{x^2} - 20x + 500\)
Doanh thu khi bán hết \(x\) mét lưới là 220\(x\) (nghìn đồng)
Hàm lợi nhuận khi bán hết \(x\) mét lưới
\(\begin{array}{l}L(x) = 220x - C(x)\\L(x) = - {x^3} + 3{x^2} + 240x - 500\end{array}\)
\(\begin{array}{l}L'(x) = - 3{x^2} + 6x + 240\\L'(x) = 0 \Leftrightarrow \left[ \begin{array}{l}x = 10\\x = - 8\end{array} \right.\end{array}\)
Bảng biến thiên
Lợi nhuận tối đa của gia đình đan lưới trong một ngày là 1200 (nghìn đồng)
Lời giải
Dựa vào đồ thị ta có \(d = 20\), tiếp theo ta tìm các hệ số \(a,b,c\) bằng cách giải hệ
\(\left\{ \begin{array}{l}a{30^3} + b{30^2} + c30 + 20 = 50\\a{50^3} + b{50^2} + c50 + 20 = 20\\a{80^3} + b{80^2} + c80 + 20 = 20\end{array} \right. \Leftrightarrow \left\{ \begin{array}{l}900a + 30b + c = 1\\250a + 50b + c = 0\\6400a + 80b + c = 0\end{array} \right. \Leftrightarrow \left\{ \begin{array}{l}a = \frac{1}{{1000}}\\b = - \frac{{13}}{{100}}\\c = 4\end{array} \right.\).
Ta được \(f\left( x \right) = \frac{1}{{1000}}{x^3} - \frac{{13}}{{100}}{x^2} + 4x + 20\). Do đó
\(\begin{array}{l}f'\left( x \right) = \frac{3}{{1000}}{x^2} - \frac{{13}}{{50}}x + 4;f'\left( x \right) = 0 \Leftrightarrow \left[ \begin{array}{l}x = \frac{{200}}{3}\\x = 20\end{array} \right.\\\end{array}\).
Ta được chiều cao lớn nhất là \(h = f\left( {20} \right) = 56\left( {\rm{m}} \right)\). Vì vậy tốc độ của tàu lượn xuống dốc là \(v\left( x \right) = \sqrt {2g \cdot \left( {56 - f\left( x \right)} \right)} \left( {{\rm{m}}/{\rm{s}}} \right)\). Vì \(g\)là hằng số nên tốc độ cực đại của biểu thức đạt được tại cực tiểu của \(f\left( x \right)\), hay \({v_{\max }}\left( x \right) = v\left( {\frac{{200}}{3}} \right) \approx 31.56\left( {{\rm{m/s}}} \right)\).
Câu 3
a) Hàm số đồng biến trên khoảng \(\left( { - \infty ; - 2} \right)\).
Đúng
Sai
b) Biết rằng hàm số \(y = f\left( x \right)\) có đồ thị đi qua điểm \(A\left( {1;3} \right)\) và đạt giá trị nhỏ nhất trên đoạn \(\left[ { - 1;2} \right]\) tại \(x = 1\). Khi đó: \(f\left( { - 1} \right) + f\left( 2 \right) - 2f\left( 1 \right) > 0\).
Đúng
Sai
c) Hàm số \(y = f\left( x \right)\) có \(2\) điểm cực tiểu.
Đúng
Sai
d) Hàm số đạt cực đại tại \(x = 2\).
Đúng
Sai
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Câu 5
A.\( - \frac{4}{3}\) .
B. \( - 3\).
C. \(\frac{3}{8}\).
D. \( - \frac{3}{8}\) .
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Câu 6
A. \(0\).
B. \(2\).
C. \(18\).
D. \( - 2\).
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Nhắn tin Zalo
Hỏi bài tập