KWAY - Trao đổi thông tin
Giới hạn- Thời gian: 0.301s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho một mạng thông tin gồm n trạm và m đường nối hai chiều giữa các trạm. Trạm s là trạm chỉ huy, trạm f là trạm điều khiển. Sau một lần bị tin tặc tấn công lấy mất dữ liệu từ trạm chỉ huy chuyển đến trạm điều khiển, chỉ huy mạng quyết định chia thông tin chuyển đi thành k đơn vị thông tin để chuyển theo k đường đến trạm điều khiển. Mà hai đường truyền bất kỳ không được chung bất kỳ một đường nào.
Hãy tìm cách truyền k đơn vị thông tin sao cho tổng chi phí là nhỏ nhất.
Input
- Dòng đầu là n, m, k, s, f (n ≤ 100).
- m dòng tiếp là u, v, c cho biết có đường từ u -> v và v -> u với chi phí là c.
Output
- Dòng đầu ghi –1 nếu không thể chuyển k đơn vị thông tin theo cách trên, ngược lại ghi chi phi để chuyển.
- k dòng tiếp lần lượt ghi cách chuyển của từng đơn vị thông tin. Số đầu là số lượng trạm trên đường truyền, tiếp đó là dãy các trạm trên đường truyền (bắt đầu từ s, kết thúc ở f)
Chú ý: Phạm vi tính toán là Longint.
Example
Input 8 11 3 1 8 1 2 1 1 4 1 1 5 1 2 3 1 2 4 1 2 7 1 3 8 1 3 6 1 3 5 1 6 8 1 7 8 1 Output 11 4 1 2 3 8 5 1 5 3 6 8 5 1 4 2 7 8
- Người up: dtmp