Một người du lịch muốn xuất phát từ thành phố , đi thăm tất cả thành phố khác, mỗi thành phố đúng một lần và cuối cùng quay trở về thành phố . Chi phí đi lại giữa hai thành phố bất kỳ được cho trước. Hãy tìm một hành trình có tổng chi phí là nhỏ nhất.
Dữ liệu:
Dòng đầu tiên chứa số nguyên - số thành phố.
dòng tiếp theo, mỗi dòng chứa số nguyên. Số ở hàng , cột là chi phí để đi từ thành phố đến thành phố .
Kết quả: Một số nguyên duy nhất là tổng chi phí nhỏ nhất của hành trình tìm được.
Ví dụ:
Dữ liệu:
4
0 20 42 35
20 0 30 34
42 30 0 12
35 34 12 0
Kết quả:
97
Giải thích:
Hành trình tối ưu là với tổng chi phí là . (Lưu ý: ví dụ này có thể không chính xác, TSP là bài toán khó). Ví dụ đúng hơn: có chi phí .
