Hiện nay, với tình hình dịch COVID diễn biến phức tạp, rất nhiều người dân đã không đi mua hàng trực tiếp mà chọn cách mua hàng online, chính vì vậy mà các Shipper rất bận rộn.
Mạng lưới giao thông ở Sơn La được xem như một đồ thị có hướng gồm đỉnh là nhà các hộ dân (đánh số từ đến ), cung có hướng là các con đường (một chiều) nối từ nhà hộ dân này tới nhà hộ dân kia.
Có một điểm tập kết hàng của hãng SHIPPING Express đặt tại nhà dân đánh số . Có đơn hàng cần vận chuyển tới nhà các hộ dân .
Tại mỗi thời điểm có thể vận chuyển số đơn hàng tùy ý, chi phí để vận chuyển các đơn hàng qua mỗi con đường bằng chính số lượng đơn hàng vận chuyển qua đó. Bạn hãy giúp hãng SHIPPING Express tính chi phí tối thiểu để vận chuyển hết đơn hàng (giả thiết luôn đảm bảo vận chuyển được hết các đơn hàng).
Dữ liệu:
Dòng đầu tiên gồm ba số nguyên ;
Dòng thứ hai (nếu ) gồm số nguyên dương ;
dòng tiếp theo, mỗi dòng gồm hai số nguyên với ý nghĩa có con đường một chiều nối từ nhà hộ dân tới nhà hộ dân .
Kết quả:
Ghi ra chi phí nhỏ nhất để vận chuyển hết đơn hàng.
