Sắp xếp
Xem dạng PDF
Gửi bài giải
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Điểm:
0,28 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
Cho một dãy số. Bạn cần sắp xếp dãy số bằng cách đổi chỗ các cặp phần tử. Chi phí để đổi chỗ phần tử hai ở vị trí i và vị trí j là ~C_{ij}~ .
Nhiệm vụ của bạn là tìm chi phí nhỏ nhất để có thể sắp xếp dãy số theo thứ tự tăng dần.
Input
- Dòng đầu tiên chứa dãy số cần sắp xếp, có số phần tử không vượt quá ~7~.
- Dòng thứ ~i~ trong số ~N~ dòng tiếp theo chứa ~N~ số nguyên, số thứ ~j~ cho biết ~C_{ij}~, chi phí để đổi chỗ phần tử ở vị trí thứ ~i~ và vị trí thứ ~j~. Biết ~N~ là số phần tử của dãy số, các phần tử được đánh số từ ~1~ đến ~N~ từ trái sang phải. ~0 \leq C_{ij} \leq 999~, ~C_{ii} = 0~ và ~C_{ij} = C_{ji}~.
Output
In ra một số nguyên dương duy nhất: tổng chi phí nhỏ nhất để sắp xếp dãy số theo thứ tự tăng dần.
Sample Input
1 2 3 4 6 5
0 1 2 3 4 5
1 0 1 2 3 4
2 1 0 1 2 3
3 2 1 0 1 2
4 3 2 1 0 900
5 4 3 2 900 0
Sample Output
4
Bình luận
ai cho xin thuật toán được không ạ:(((