Thăm Viếng Đền Đài
Points
30
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Đề bài
Có $N$ ngôi đền được đánh số từ $0$ đến $N-1$. Bạn bắt đầu từ đền $0$ và muốn thăm tất cả các đền. Chi phí đi từ đền $i$ đến đền $j$ là $c_{i,j}$. Hãy tìm chi phí nhỏ nhất để thăm tất cả các đền (không cần quay về đền $0$).
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$.
- $N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên biểu diễn ma trận chi phí.
Dữ liệu ra
- In ra chi phí nhỏ nhất.
Ví dụ
| Input | Output |
|---|---|
| 4 0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0 |
65 |
Giới hạn
- $2 \le N \le 15$
- $1 \le c_{i,j} \le 10^6$ (với $i \ne j$)
- $c_{i,i} = 0$
Community Discussion