| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P141PROD - ROUND 1D - Hành trình đặc biệt |
Trong giấc mơ, Tí thấy mình đang ở trong một vương quốc cổ đẹp với rất nhiều những hòn đảo và cây cầu. Tí muốn đi tham quan tất cả các hòn đảo với chi phí nhỏ nhất có thể. Đang bước đi dạo quanh con sông, Tí tình cờ gặp Tèo và cả hai cùng bắt đầu hành trình.
Tuy nhiên, Tèo muốn sắp xếp một hành trình hợp lý, sao cho mỗi hòn đảo chỉ đến thăm duy nhất một lần, và trước khi đến thăm hòn đảo thứ K, thì tất cả các hòn đảo có nhãn nhỏ hơn K đã phải được thăm rồi hoặc sẽ được thăm sau đó.
Các bạn hãy giúp Tí và Tèo xây dựng dựng hành trình du lịch tối ưu nhất!
Input
Dòng đầu tiên là số nguyên dương N là số hòn đảo (1 <= N <= 1500).
N dòng tiếp theo, mỗi dòng gồm N số trong khoảng từ 0-> 1000. Số c_AB ở hàng A, cột B thể hiện chi phí đi lại giữa thành phố A và B (dĩ nhiên luôn bằng với số ở hàng B, cột A). Nếu A = B, c_AB = 0.
Output
In ra một số nguyên dương duy nhất là chi phí nhỏ nhất cho hành trình.
Example
Test 1:
Input:
3
0 5 2
5 0 4
2 4 0
Output:
7
Giải thích test 1: Hành trình tối ưu là 2, 1, 3 hoặc 3, 1, 2. Hành trình 1, 3, 2 có chi phí nhỏ hơn nhưng không thỏa mãn điều kiện mà Tèo đưa ra.
Test 2:
Input:
4
0 15 7 8
15 0 16 9
7 16 0 12
8 9 12 0
Output:
31
Giải thích test 2: Hành trình tối ưu là 3, 1, 2, 4 hoặc 4, 2, 1, 3.
| Được gửi lên bởi: | adm |
| Ngày: | 2014-01-04 |
| 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 JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
