Cho thành phố và ma trận chi phí là chi phí đi từ thành phố đến thành phố . Hãy tìm một hành trình bắt đầu từ thành phố , đi qua mỗi thành phố khác đúng một lần và quay trở về thành phố với tổng chi phí là nhỏ nhất.
Dữ liệu:
Dòng đầu tiên là số nguyên ().
dòng tiếp theo, mỗi dòng chứa số nguyên, mô tả ma trận chi 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.
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 chi phí . Bài toán này là ứng dụng kinh điển của Quy hoạch động Bitmask, trong đó trạng thái DP được biểu diễn bằng một mặt nạ bit.
