BA THÀNH PHỐ TRONG MỘT ĐẤT NƯỚC CÓ N THÀNH PHỐ ĐƯỢC ĐÁNH DẤU TỬ...
Bài 3. Ba thành phố
Trong một đất nước có N thành phố được đánh dấu tử 1 đến N. Có một số
thành phố được nối với nhau bởi hệ thống các con đường cao tốc, mỗi con
đường nối hai thành phố nào đó. Hệ thống đường cao tốc này có tính chất sau:
Đối với hai thành phố bất kỳ A và B, nếu có cách di chuyển từ thành phố A
đến thành phố B theo các con đường cuả hệ thống thì có đúng một cách di
chuyển mà trong đó không có con đường nào bị đi qua quá một lần.
Tổng thống của đất nước này đặt ra câu hỏi sau đây đối với các nhà Tin học:
Ba thành phố nào là cách xa nhau nhất. Chính xác hơn, ta gọi độ giãn cách
giữa ba thành phố A, B và C là tổng số con đường cần sử dụng để di chuyển
từ A đến B, tiếp đến di chuyển từ B đến C và cuối cùng di chuyển từ C đến A
tuân thủ điều kiện: trong mỗi di chuyển vừa nêu, mỗi con đường chỉ được đi
qua không quá một lần.
Yêu cầu: Tìm ba thành phố mà độ giãn cách giữa chúng là lớn nhất.
Ví dụ:
Đối với 5 thành phố với các con đường nối chúng được cho trong hình 1, ba
thành phố với độ giãn cách lớn nhất là 1, 2 và 5 (độ giãn cách là 2+3+3 = 8).
Đối với 5 thành phố với các con đường nối chúng được cho trong hình 2, ba
thành phố với độ giãn cách lớn nhất là ba thành phố bất kỳ trong tập 4 thành
phố {1, 2, 4, 5} (độ giãn cách là 2+2+2 = 6).
1
2
1
3
4
5
Dữ liệu: Vào file văn bản COUNTRY.INP
Dòng đầu tiên chứa số nguyên N (3≤N≤10000).
Tiếp theo là N dòng mô tả thông tin về các thành phố. Dòng thứ i chứa
các số: K
i