HỆ RÀNG BUỘC

Cho n biến số nguyên v₁, v₂,…,v_n và một tập m ràng buộc. Mỗi ràng buộc được biểu diễn bởi 3 số nguyên i, j, c có dạng v_j-v_i<=c (c là số nguyên).

Hãy tìm cách gán giá trị nguyên nằm trong phạm vi [a,b] cho các biến v₁, v₂,…,v_n để thỏa mãn tất cả m ràng buộc đã cho.

Dữ liệu vào: Từ tệp văn bản SDC.INP bao gồm:

+ Dòng đầu chứa 4 số nguyên dương n, m,a, b với n<=1000, m<=10000, a<b<=10⁶;

+ Mỗi dòng trong m dòng tiếp theo chứa 3 số nguyên i, j, c tương ứng với một ràng buộc (1<=i, j<=n; |c|<=10⁶)

Dữ liệu ra: ghi vào tệp văn bản SDC.OUT bao gồm:

+ Dòng 1 ghi từ YES nếu có phương án thực hiện, ghi từ NO nếu không có phương án.

+ Trong trường hợp có phương án thực hiện, dòng 2 ghi n giá trị của v₁, v₂,…,v_n tìm được.

Các số trên dòng của tệp SDC.INP và SDC.OUT được ghi cách nhau ít nhất 1 dấu cách.

Ví dụ:

SDC.INP	SDC.OUT
3 3 1 4 1 2 5 2 3 -2 3 1 -1	YES 1 4 2

Solution Test Code