Hè đến rồi, mùa du lịch lại đến, gia đình bạn có kế hoạch đi du lịch ở đâu chưa? Còn gia đình Lan đang có kế hoạch đi du lịch thăm thành phố, mỗi thành phố đúng một lần. Sau khi tham khảo các nhà cung cấp dịch vụ thì gia đinh Lan nhận được thông tin chi phí đi lại giữa hai thành phố bất kỳ, Lan đang băn khoăn không biết nên đi theo hành trình như thế nào để tiết kiệm nhất? Bạn hãy giúp gia đình Lan nhé.
Cho biết là số thành phố (đánh số từ đến ) và mảng gồm số nguyên không âm với là chi phí đi từ thành phố đến thành phố ( có thể khác với mọi ). Nhà Lan xuất phát từ thành phố . Hãy tìm một hành trình đi qua tất cả các thành phố, mỗi thành phố đúng một lần rồi quay về thành phố với tổng chi phí thấp nhất.
Dữ liệu vào:
Dòng đầu chứa số nguyên là số thành phố;
dòng tiếp theo mô tả mảng : Dòng thứ chứa số nguyên
Dữ liệu ra:
Dòng đầu ghi số nguyên không âm là chi phí nhỏ nhất;
Dòng thứ hai liệt kê theo thứ tự các thành phố đi qua ( số dương, mỗi số cách nhau bởi một dấu cách).
Ví dụ:
Dữ liệu vào:
4
0 20 35 42
20 0 34 30
35 34 0 12
42 30 12 0
Dữ liệu ra:
97
1 2 4 3 1
Giải thích:
Hành trình có tổng chi phí là là chi phí thấp nhất.
