Question

[Đỗ Đức Hà]

Chúng ta có một bản đồ các thành phố như hình dưới đây. Mỗi đỉnh của hình là một thành phố. Cạnh nối hai đỉnh với nhau chính là đường để đi đến nhau của hai thành phố. Nghỉ hè bố mẹ sẽ cho bạn Hoa đi tham quan.

Hoa đã điền điểm số cho mỗi thành phố lên bản đồ dưới đây (số ghi trên mỗi ô biểu thị thành phố chính là số điểm thể hiện độ yêu thích của hoa cho thành phố ấy). Bạn hãy tính toán một chương trình du lịch cho Hoa và gia đình sao cho cả gia đình có thể đi được 5 thành phố liên tiếp nhau và có tổng số điểm yêu thích lớn nhất.