BCTSP2 - Travelling Salesman Problem 2
Một người du lịch muốn tham quan n thành phố T1, …, Tn. Xuất phát từ 1 thành phố nào đó, người du lịch muốn đi qua tất cả thành phố còn lại, mỗi thành phố đi qua đúng một lần rồi quay trở lại thành phố xuất phát.
Gọi C[i][j] là chi phí đi từ thành phố Ti đến Tj. Hãy tìm một hành trình thỏa mãn yêu cầu của bài toán sao cho chi phí là nhỏ nhất.
Lưu ý: Bài TSP 2 nhằm mục đích luyện tập cho thuật toán tham lam, thuật toán này không đảm bảo luôn tìm ra đáp án tối ưu, tuy nhiên với mục đích luyện tập test của TSP 2 được chọn để tham lam cũng tìm ra được đáp án tối ưu.
Input
Dòng đầu tiên gồm số nguyên n (0 < n <= 1000) – là số thành phố
N dòng tiếp theo, dòng thứ i nhập n số nguyên C[i][j] (0 <= j < n, 0 < C[i][j] <= 10^9) – là chi phí đi từ thành phố Ti đến Tj và ngược lại
Output
In ra chi phí nhỏ nhất có thể đạt được
Example
Input:
44 0 20 35 42 20 0 34 30 35 34 0 12 42 30 12 00 20 35 4220 0 34 3035 34 0 1242 30 12Output: 97
Added by: | adm |
Date: | 2016-07-17 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |