Để chuẩn bị cho Lễ hội Hoa Ban và quảng bá nghệ thuật Xòe Thái – Di sản văn hóa phi vật thể của nhân loại, một đoàn nghệ thuật xuất phát từ Thành phố Sơn La (được đánh số là địa điểm ) dự định đi qua tất cả huyện và bản làng trọng điểm khác trong tỉnh để biểu diễn.
Tỉnh Sơn La có địa điểm cần ghé thăm, được đánh số từ đến . Do địa hình đồi núi hiểm trở, chi phí di chuyển (bao gồm xăng xe và thời gian) giữa các địa điểm có sự khác biệt. Chi phí đi trực tiếp từ địa điểm đến địa điểm được cho bởi giá trị trong một ma trận chi phí .
Đoàn nghệ thuật cần lập một kế hoạch di chuyển bắt đầu từ Thành phố Sơn La (địa điểm ), đi qua tất cả các địa điểm còn lại đúng một lần để biểu diễn, sau đó quay trở về Thành phố Sơn La để kết thúc hành trình. Bạn hãy giúp đoàn tìm một lộ trình sao cho tổng chi phí di chuyển là nhỏ nhất.
Cụ thể, tìm một hoán vị của tập hợp các địa điểm với sao cho giá trị sau đây đạt tối thiểu:
Dữ liệu:
Dòng đầu tiên chứa số nguyên dương ().
dòng tiếp theo, mỗi dòng chứa số nguyên không âm. Số thứ ở dòng thứ đại diện cho chi phí di chuyển từ địa điểm đến địa điểm ().
Quy ước với mọi .
Kết quả:
In ra một số nguyên duy nhất là tổng chi phí di chuyển thấp nhất của hành trình tìm được.
Ví dụ:
Dữ liệu:
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0
Kết quả:
35
Ví dụ 2:
Dữ liệu:
3
0 1 5
2 0 3
1 4 0
Kết quả:
5
Giải thích:
Ở ví dụ 2: Lộ trình tối ưu là Thành phố Sơn La (1) Địa điểm 2 Địa điểm 3 Thành phố Sơn La (1) với tổng chi phí: .
