Bạn đang chơi một trò chơi có địa điểm và chuyến bay một chiều giữa chúng. Mục tiêu của bạn là bay từ địa điểm đến địa điểm . Mỗi chuyến bay sẽ làm thay đổi điểm số của bạn. Điểm số ban đầu là .
Bạn hãy tìm đường đi từ đến sao cho tổng điểm số là lớn nhất có thể.
Lưu ý: Có thể có những chu trình mà khi đi qua đó, điểm số của bạn sẽ tăng lên mãi mãi. Nếu tồn tại một đường đi từ đến mà có thể đi qua một chu trình như vậy, thì điểm số có thể là vô hạn.
Dữ liệu:
Dòng đầu tiên chứa hai số nguyên và : số địa điểm và số chuyến bay.
dòng tiếp theo, mỗi dòng chứa ba số nguyên : có một chuyến bay từ đến và điểm số của bạn tăng thêm .
Kết quả: In ra một số nguyên duy nhất là điểm số lớn nhất có thể đạt được. Nếu điểm số có thể lớn vô hạn, in ra -1.
Ví dụ:Dữ liệu:
4 5
1 2 3
2 4 5
1 3 2
3 4 3
1 4 10
Kết quả:
10
Giải thích:
Bài toán tìm đường đi dài nhất có thể được chuyển thành bài toán tìm đường đi ngắn nhất bằng cách đổi dấu trọng số các cạnh. Thuật toán Bellman-Ford có thể được sử dụng để giải quyết bài toán này và phát hiện các chu trình có tổng trọng số dương (tức chu trình âm trong bài toán đường đi ngắn nhất tương đương).
