Tuyến Ống Nước Tân Hiệp Chi Phí Nhỏ Nhất

Mô tả

Nhà máy nước Tân Hiệp đang triển khai dự án kéo đường ống nước sạch đến khu dân cư. Mạng lưới được mô hình hóa như một đồ thị gồm các điểm lắp đặt và các đoạn ống nối giữa chúng. Mỗi đoạn ống đều có chi phí lắp đặt (trọng số) là một số nguyên dương.

Bạn được giao nhiệm vụ tìm tổng chi phí lắp đặt nhỏ nhất để kéo ống từ nhà máy (điểm xuất phát) đến một trạm bơm cụ thể (điểm đích). Đôi khi không có đường ống nào nối đến trạm đích, khi đó hãy trả về -1.

Đầu vào

• Dòng đầu tiên chứa hai số nguyên n (số lượng điểm) và m (số lượng đoạn ống). Các điểm được đánh số từ 0 đến n-1.
• Dòng thứ hai chứa hai số nguyên s (điểm xuất phát) và t (điểm đích).
• m dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, w mô tả một đoạn ống nối điểm u và v với chi phí lắp đặt là w.

Đầu ra

• In ra một số nguyên duy nhất là tổng chi phí lắp đặt nhỏ nhất, hoặc -1 nếu không thể đến được trạm đích.

Ràng buộc

• 2 <= n <= 10^4
• 0 <= m <= 10^5
• 0 <= s, t < n
• 0 <= u, v < n
• 1 <= w <= 10^6

Ví dụ

Input: text 4 5 0 3 0 1 2 0 2 5 1 2 1 1 3 7 2 3 1

Output: text 4

Giải thích: Từ nhà máy nước ở điểm 0 (Tân Hiệp), ta cần đến trạm bơm 3.

• Đi thẳng từ 0 đến 3 tốn 7.
• Đi 0 -> 1 -> 3 tốn 2 + 7 = 9.
• Đi 0 -> 1 -> 2 -> 3 tốn 2 + 1 + 1 = 4. Vậy chi phí nhỏ nhất là 4.