Chia vương quốc
Đề bài
Mô tả
Vương quốc Byteland có thành phố, đánh số từ đến . Vương quốc có đúng con đường, mỗi con đường nối một cặp thành phố. Dùng các con đường này, có thể đi từ một thành phố bất kỳ đến mọi thành phố khác.
Nhà vua của Byteland muốn chia vương quốc thành hai nửa và trao mỗi nửa cho một trong hai người con trai. Việc chia được thực hiện bằng cách bỏ đi đúng một con đường, tách vương quốc thành hai thành phần liên thông.
Hóa ra đây không phải là việc đơn giản! Để tránh hai người con tranh chấp, nhà vua cần chia vương quốc một cách công bằng. Với mỗi nửa, nhà vua định nghĩa đường kính của nó là độ dài đường đi đơn dài nhất nối hai thành phố trong nửa đó. Nhà vua muốn hiệu giữa đường kính của hai nửa là nhỏ nhất.
Lưu ý: một đường đi đơn từ thành phố đến thành phố là một dãy thành phố , trong đó , và các đôi một khác nhau. Với mọi chỉ số hợp lệ, và được nối trực tiếp bởi một con đường. Độ dài của đường đi là tổng độ dài các con đường nối và .
Hãy giúp nhà vua!
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ dữ liệu, mỗi bộ dữ liệu có dạng:
- Dòng đầu tiên chứa một số nguyên dương (): số thành phố.
- dòng tiếp theo, dòng thứ () chứa hai số nguyên và (, ), cho biết hai thành phố và được nối bởi một con đường có độ dài .
Dữ liệu vào kết thúc bằng một dòng chứa số , dòng này không phải là một bộ dữ liệu.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên: hiệu nhỏ nhất giữa đường kính của hai nửa.
Ràng buộc
- , tổng qua tất cả các bộ dữ liệu không vượt quá .
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 12 1 3 1 3 3 2 1 3 1 5 2 1 7 2 8 2 9 3 8 2 11 3 4 1 10 2 10 3 10 4 1 20 2 10 3 10 0 |
0 0 10 |
Ở bộ dữ liệu thứ nhất, một cách tối ưu là bỏ con đường nối thành phố và : nửa chứa thành phố gồm các thành phố có đường kính dài ; nửa còn lại có đường kính dài . Ở bộ thứ ba, bỏ con đường nối thành phố và : hai nửa có đường kính và . |
| 2 1 5 3 1 4 1 9 3 1 6 2 6 5 1 1 1 2 1 3 1 4 0 |
0 4 6 5 |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ nhất: hai nửa đều là một thành phố, đường kính . Bộ thứ hai: bỏ con đường dài , hai nửa có đường kính và . Bộ thứ ba: mọi cách đều cho đường kính và . Bộ thứ tư: bỏ con đường dài , nửa còn lại có đường kính . |
Bình luận