Cho một đồ thị có hướng, có trọng số gồm đỉnh và cạnh. Tìm đường đi ngắn nhất về mặt trọng số từ đỉnh đến đỉnh , với điều kiện bổ sung là đường đi đó không được chứa nhiều hơn cạnh.
Dữ liệu:
Dòng đầu tiên chứa bốn số nguyên .
dòng tiếp theo, mỗi dòng chứa ba số nguyên mô tả một cạnh có hướng từ đến với trọng số .
Kết quả: Một số nguyên duy nhất là độ dài đường đi ngắn nhất tìm được. Nếu không có đường đi nào từ đến thỏa mãn điều kiện, in ra .
Ví dụ:
Dữ liệu:
4 4 2 1 4
1 2 1
2 4 10
1 3 3
3 4 4
Kết quả:
7
Giải thích:
Đường đi có độ dài và dùng 2 cạnh.
Đường đi có độ dài và dùng 2 cạnh.
Đường đi ngắn nhất thỏa mãn điều kiện có độ dài là 7.
