Chênh Lệch Tỷ Giá Ngoại Tệ

Buổi 41 — SPFA & Bellman-Ford
Points
60
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Thị trường ngoại hối có N loại tiền tệ (đánh số từ 1 đến N) và M quy tắc quy đổi một chiều. Quy tắc u v r cho biết 1 đơn vị tiền tệ u có thể đổi thành r đơn vị tiền tệ v. Hãy kiểm tra xem có tồn tại cơ hội kinh doanh chênh lệch giá (Arbitrage) hay không — tức là tồn tại một chu trình đổi tiền xuất phát từ một loại tiền tệ và quay về chính nó sao cho số tiền thu được lớn hơn hẳn ban đầu.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên N và M.
  • M dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v và một số thực r.
Dữ liệu ra
  • In ra YES nếu tồn tại chu trình Arbitrage, ngược lại in ra NO.
Ví dụ
Input Output
3 3
1 2 2.0
2 3 0.5
3 1 1.1
YES
3 3
1 2 2.0
2 3 0.5
3 1 0.9
NO
Giới hạn
  • 1 ≤ N ≤ 1000
  • 0 ≤ M ≤ 5000
  • 1 ≤ u, v ≤ N
  • 0.001 ≤ r ≤ 1000.0
Draft saved