Sắp xếp
View as PDF
Submit solution
Points:
0.28 (partial)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
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
Comments
ai cho xin thuật toán được không ạ:(((