Tuyết không thành vấn đề
Đề bài
Mô tả
Học viện Kỹ thuật và Công nghệ Yllihc (YETI), nằm ở miền bắc xứ Snowblovia, có hai vấn đề: tuyết và tiền. Cụ thể là họ có quá nhiều thứ thứ nhất và không đủ thứ thứ hai. Mỗi mùa đông (và cả mùa thu lẫn mùa xuân) khuôn viên trường bị phủ kín bởi những lớp tuyết dày, và các vỉa hè nối các tòa nhà trong trường không thể đi lại được. Để tiếp tục hoạt động, YETI cần dọn tuyết trên các vỉa hè nối các tòa nhà. Vì ngân sách eo hẹp, các vỉa hè này là một tập tối thiểu đảm bảo giữa hai tòa nhà bất kỳ luôn có đường đi.
Với số tiền tiết kiệm được nhờ không xây thêm vỉa hè, YETI đã mua hai máy thổi tuyết. Để dọn tuyết, hai nhân viên đưa hai máy thổi tuyết ra khỏi tòa nhà (hoặc các tòa nhà) đang cất chúng và đẩy máy dọc theo các vỉa hè để dọn tuyết. Mỗi vỉa hè phải được đi qua ít nhất một lần. Mỗi máy thổi tuyết, sau khi dọn xong, được cất vào tòa nhà mà nó đang ở cạnh (và ở trận tuyết tiếp theo, các máy sẽ được đẩy theo chiều ngược lại, cứ thế suốt mười một tháng của mùa tuyết).
Đội bảo trì của YETI muốn chọn tòa nhà cất các máy thổi tuyết và thiết kế lộ trình đẩy từng máy sao cho tổng quãng đường hai máy phải đi ngoài trời lạnh là nhỏ nhất (để bảo vệ cả thiết bị quý giá lẫn nhân viên khỏi bị đóng băng). Lưu ý rằng lộ trình có thể đi qua cả những vỉa hè đã được dọn, như hình dưới đây minh họa một lời giải tối ưu cho Ví dụ 1: một máy đi (màu xanh lam, dài ), máy còn lại đi (màu đỏ, dài ).
graph weighted 7 6 1 4 2 2 4 3 3 4 1 4 5 1 5 6 2 5 7 4 path blue 1 4 5 6 path red 2 4 3 highlight red 5-7
YETI muốn nhờ Khoa Khoa học Máy tính giải quyết việc này, nhưng khoa đã bị xóa sổ trong Trận Bão Tuyết Lớn năm 2006, nên họ tìm đến bạn.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên , số tòa nhà trong khuôn viên YETI. Các tòa nhà được đánh số từ đến .
Mỗi dòng trong dòng tiếp theo chứa ba số nguyên , và , cho biết có một vỉa hè độ dài nối hai tòa nhà và .
Dữ liệu ra
In ra tổng quãng đường nhỏ nhất mà hai máy thổi tuyết phải đi để dọn tuyết trên mọi vỉa hè.
Ràng buộc
- .
- , , .
- Các vỉa hè nối mọi tòa nhà với nhau (giữa hai tòa nhà bất kỳ có đúng một đường đi).
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 1 4 2 2 4 3 3 4 1 4 5 1 5 6 2 5 7 4 |
15 | Như hình trên: lộ trình dài và lộ trình dài , tổng . |
| 4 1 2 1 2 3 2 3 4 3 |
6 | Các vỉa hè tạo thành một đường thẳng : một máy đi từ đến (dài ), máy còn lại không cần đi. |
Bình luận