Chỉ còn vài ngày nữa thôi là chúng ta sẽ đón Tết Nguyên Đán, gia đình của TINEZ đang tất bật chuẩn bị quần áo mới và lên kế hoạch đi du xuân đầu năm. Có ( ) địa điểm mà gia đình của TINEZ muốn đi thăm vào những ngày đầu năm mới này. Mỗi địa điểm chỉ được thăm đúng 1 lần và sau khi thăm hết N địa điểm đó thì cả nhà sẽ quay trở về địa điểm bắt đầu. Giữa 2 vị trí và ( , ) có 1 con đường 2 chiều giữa 2 vị trí đó. Thế nhưng, việc di chuyển giữa 2 địa điểm và sẽ khiến gia đình của TINEZ tốn (đồng) ( ) tiền đổ xăng để di chuyển qua tuyến đường này. Gia đình của TINEZ đang không biết liệu rằng lượng tiền đổ xăng ít nhất cần phải chi để đi qua tất cả các địa điểm này. TINEZ hiện tại đang bận chơi Tết nên quên hết cách code để tìm ra phương án cho bài toán “hóc búa” này nên anh ấy muốn nhờ bạn giải quyết bài toán này.
Input
- Dòng đầu chứa số nguyên là số địa điểm
- dòng tiếp theo, mỗi dòng chứa số là chi phí để di chuyển giữa 2 vị trí và
Output
- Đưa ra 1 số duy nhất chính là chi phí nhỏ nhất để thăm tất cả địa điểm sau đó quay về địa điểm bắt đầu
Constraint
Subtasks
- Subtask 1 (80%):
- Subtask 2 (20%):
Sample Input
Copy
4
0 10 15 20
10 0 25 25
15 25 0 30
20 25 30 0
Sample Output
Copy
80
Notes
Một phương án đi hết tất cả các địa điểm là: . Và đây cũng là phương án có chi phí nhỏ nhất: .
Bình luận