Phân công chi nhánh
Đề bài
Mô tả
Công ty Sản phẩm Tiêu dùng Sáng tạo (ICPC) đang lên kế hoạch khởi động một dự án tuyệt mật. Dự án gồm dự án con. Có chi nhánh của ICPC tham gia dự án và ICPC muốn giao mỗi chi nhánh cho một trong các dự án con. Nói cách khác, các chi nhánh sẽ được chia thành nhóm rời nhau, mỗi nhóm phụ trách một dự án con.
Vào cuối mỗi tháng, mỗi chi nhánh sẽ gửi một thông điệp tới mọi chi nhánh khác trong cùng nhóm của nó (mỗi chi nhánh nhận một thông điệp khác nhau). ICPC có một giao thức liên lạc riêng. Mỗi chi nhánh có một khóa bí mật mà chỉ chi nhánh đó và trụ sở chính của ICPC biết. Giả sử chi nhánh muốn gửi một thông điệp tới chi nhánh . Chi nhánh mã hóa thông điệp bằng khóa của mình. Một người đưa thư tin cậy nhận thông điệp này tại chi nhánh và mang nó tới trụ sở chính của ICPC. Trụ sở giải mã thông điệp bằng khóa rồi mã hóa lại bằng khóa . Sau đó người đưa thư mang thông điệp mới được mã hóa tới chi nhánh , nơi nó được giải mã bằng khóa của chi nhánh đó. Vì lý do an ninh, mỗi người đưa thư chỉ được mang một thông điệp mỗi lần.
Cho một mạng lưới đường đi cùng vị trí của các chi nhánh và trụ sở chính trong mạng lưới này, hãy xác định tổng quãng đường nhỏ nhất mà những người đưa thư cần đi để chuyển hết các thông điệp cuối tháng, xét trên mọi cách phân chia các chi nhánh vào các dự án con.
Dữ liệu vào
Dòng đầu tiên chứa bốn số nguyên , , và , trong đó là số giao lộ, là số chi nhánh, là số dự án con và là số con đường. Các giao lộ được đánh số từ tới . Các chi nhánh nằm ở các giao lộ tới , còn trụ sở chính nằm ở giao lộ .
Mỗi dòng trong dòng tiếp theo chứa ba số nguyên , và , cho biết có một con đường một chiều từ giao lộ tới một giao lộ khác với độ dài .
Dữ liệu ra
In ra tổng quãng đường nhỏ nhất mà những người đưa thư cần đi.
Ràng buộc
- , , , .
- , , .
- Không có cặp có thứ tự nào xuất hiện quá một lần.
- Từ mọi giao lộ đều có thể đi tới mọi giao lộ khác.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 4 2 10 5 2 1 2 5 1 3 5 5 4 5 0 1 5 1 2 3 1 3 2 5 2 4 5 2 1 1 3 4 2 |
13 | Trụ sở ở giao lộ . Tổng quãng đường đi từ chi nhánh tới trụ sở và từ trụ sở về chi nhánh lần lượt là , , , với các chi nhánh . Chia thành nhóm và : mỗi chi nhánh gửi một thông điệp và nhận một thông điệp, tổng là . |
| 5 4 2 10 5 2 1 2 5 1 3 5 5 4 5 10 1 5 1 2 3 1 3 2 5 2 4 5 2 1 1 3 4 2 |
24 | Các tổng quãng đường khứ hồi lần lượt là . Chia thành nhóm và : mỗi chi nhánh trong nhóm đầu gửi thông điệp và nhận thông điệp, tổng là ; chi nhánh đứng một mình không gửi gì. |
Bình luận