Đường đi ngắn nhất
Mô tả
Cho đồ thị vô hướng có trọng số dương. Tìm khoảng cách ngắn nhất từ đỉnh 1 đến đỉnh n.
Input
Dòng đầu gồm n, m. Mỗi dòng trong m dòng tiếp theo gồm u, v, w mô tả một cạnh.
Output
In khoảng cách ngắn nhất, hoặc -1 nếu không có đường đi.
Ví dụ
Input
4 4
1 2 3
2 4 5
1 3 2
3 4 4
Output
6
Với trọng số dương, thuật toán Dijkstra kết hợp danh sách kề và hàng đợi ưu tiên giúp tìm đường đi ngắn nhất hiệu quả hơn cách duyệt tất cả đường đi.
Code Editor
Code đã được lưu trên trình duyệt. Hệ thống chấm test tự động sẽ hoạt động sau khi kết nối máy chủ Judge.