| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
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
| Được gửi lên bởi: | adm |
| Ngày: | 2016-07-17 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2020-04-02 15:36:15
tham lam đâu cần đúng sai =)) |
|
|
2019-12-23 15:15:58
dùng qhđ chắc tối ưu mọi trường hợp |
|
|
2018-03-14 07:12:22
cứ tham lam mà duyệt thôi =))) |
|
|
2017-09-26 09:49:39
nhật hào sạch |
