Chi phí vận chuyển nhỏ nhất

Bối cảnh và bài toán

Mạng vận chuyển một chiều có chi phí không âm trên mỗi tuyến. Một đơn hàng cần đi từ kho s tới điểm t.

Yêu cầu

Tính tổng chi phí nhỏ nhất từ s tới t; nếu không thể tới, in -1.

Input

Dòng đầu n, m, s, t; tiếp theo m dòng u, v, w mô tả cạnh có hướng trọng số w.

Output

In chi phí ngắn nhất hoặc -1.

Ràng buộc

• 2 <= n <= 2*10^5
• 0 <= m <= 3*10^5
• 0 <= w <= 10^9 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

5 6 1 5
1 2 2
1 3 8
2 3 1
2 4 5
3 5 3
4 5 1

Output

6

Giải thích. Các trọng số không âm cho phép Dijkstra chốt dần khoảng cách nhỏ nhất tới đích.

Ví dụ 2

Input

3 1 1 3
1 2 4

Output

-1

Giải thích. Các trọng số không âm cho phép Dijkstra chốt dần khoảng cách nhỏ nhất tới đích.

Gợi ý

Hãy bắt đầu bằng cách phân loại graph, mục tiêu truy vấn và constraints; sau đó đối chiếu với Decision Map của buổi học trước khi viết code.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from Codeforces 20C – Dijkstra?. Bản FULLHOUSE DEV đã biên tập lại bối cảnh/format theo phạm vi khóa học.