Đất nước AZ. có thành phố vừa phải hứng chịu một trận động đất mạnh. Nhiều tòa nhà và các công trình công cộng bị phá hủy, làm tê liệt toàn bộ hệ thống giao thông giữa các thành phố. Sau những nỗ lực của chính phủ, có con đường hai chiều nối giữa thành phố được sửa chữa để đảm bảo tính liên thông đi lại giữa thành phố. Các thành phố được đánh số từ đến . Con đường thứ nối hai thành phố và có độ đài km. Theo dự báo, trong thời gian tới có thể xảy ra một trận động đất nữa, do đó, chính phủ đang lên kế hoạch ứng phó. Theo thông tin thu nhận được, hiện tại thành phố đang có nhân viên cứu hộ. Chính phủ muốn điều chỉnh lại số lượng nhân viên cứu hộ ở các thành phố sao cho độ chênh lệch nhân viên cứu hộ giữa các thành phố là nhỏ nhất. Độ chênh lệch nhân viên cứu hộ giữa các thành phố được tính bằng hiệu số nhân viên cứu hộ ở thành phố có nhiều nhân viên nhất với thành phố có ít nhân viên nhất.
Tại mỗi thành phố đều có xe dùng để vận chuyển nhân viên cứu hộ (giả thiết số xe tại mỗi thành phố đủ nhiều để phục vụ vận chuyển), mỗi xe có khả năng vận chuyển không quá nhân viên cứu hộ. Nếu muốn vận chuyển nhân viên cứu hộ từ thành phố sang thành phố bằng đường nối trực
tiếp thì thành phố sẽ cần xe, trong đó là số nguyên nhỏ nhất không nhỏ hơn và độ dài đường đi mà mỗi xe phải đi là . Sau khi đến thành phố , các nhân viên cứu hộ sẽ ở lại hoặc có thể tiếp tục di chuyển sang thành phố khác bằng xe của thành phố . Để tiết kiệm chi phí vận chuyển, chính phủ cần xây dựng phương án vận chuyển sao cho tổng độ dài đường đi của các xe dùng để vận chuyền là ngắn nhất mà vẫn thỏa mãn yêu cầu nêu trên.
Yêu cầu: Cho thông tin về con đường và số nhân viên cứu hộ tại mỗi thành phố. Hãy tìm phương án vận chuyển nhân viên cứu hộ mà tổng độ dài đường đi của các xe dùng vận chuyên là ngắn nhất mà vẫn đảm bảo yêu cầu độ chênh lệch nhân viên cứu hộ giữa các thành phố là nhỏ nhất.
Dữ liệu vào:
Dòng đầu chứa hai số nguyên dương và ;
Dòng thứ hai gồm số nguyên không âm ;
Dòng thứ trong số dòng tiếp theo chứa ba số nguyên thỏa mãn và .
Các số trên cùng một dòng cách nhau bởi dấu cách.
Dữ liệu ra:
Dòng đầu chứa một số nguyên là tổng độ dài ngắn nhất của các xe dùng để vận chuyển đảm bảo yêu cầu độ chênh lệch nhân viên cứu hộ giữa các thành phố là nhỏ nhất;
Dòng thứ hai chứa số nguyên là số lượng đợt vận chuyển;
Dòng thứ trong dòng tiếp theo chứa ba số nguyên dương , nghĩa là thành phố sẽ có các xe vận chuyển nhân viên cứu hộ sang thành phố (giá trị phải nhỏ hơn hoặc bằng số lượng nhân viên của thành phố tại thời điểm vận chuyển).
Giới hạn:
Có số test ứng với số điểm của bài thỏa mãn điều kiện: ;
số test khác ứng với số điểm của bài thỏa mãn điều kiện: và mỗi thành phố có không quá đường nỗi trực tiếp tới thành phố khác;
số test còn lại ứng với số điểm của bài thỏa mãn điều kiện: .
Đối với mỗi test, nếu thí sinh đưa ra đúng giá trị tổng độ dài ngắn nhất của các xe dùng để vận chuyển, thí sinh sẽ được số điểm của test đó, nếu tiếp tục đưa ra được một phương án vận chuyển đúng, thí sinh sẽ được số điểm còn lại.
Vị dụ:
Dữ liệu vào:
4 10
12 9 49 51
1 2 1
1 3 1
2 4 2
Dữ liệu ra:
7
3
3 1 19
4 2 20
1 2 1
Giải thích:
Cần hai xe vận chuyển nhân viên cứu hộ từ thành phố về thành phố và hai xe vận chuyển nhân viên cứu hộ từ thành phố về thành phố , cuối cùng cần một xe vận chuyển nhân viên từ thành phố sang thành phố . Độ chênh lệch nhân viên cứu hộ giữa các thành phố bằng và tổng độ dài đường đi của các xe là (km).
