Problem
Cho một đồ thị có hướng có trọng số với các cạnh âm (không có chu trình âm).
Cho trước một đỉnh bắt đầu và đỉnh kết thúc, hãy xác định khoảng cách tối thiểu giữa chúng.
Đầu vào:
Cho 4 số n, m, s, f - lần lượt là số đỉnh, số cạnh, đỉnh đầu và đỉnh cuối (bắt đầu từ 1).
M dòng tiếp theo mỗi dòng ghi 3 số - đỉnh 1, đỉnh 2 và giá chuyển tiếp giữa các đỉnh.
Đầu ra:
Yêu cầu hiển thị một số - câu trả lời cho nhiệm vụ. Nếu không có câu trả lời, hãy xuất Inf.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
4 2 1 4
1 2 100500
2 3 100500
|
Thông tin |