Sắp xếp

Xem dạng PDF

Gửi bài giải


Đ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:
Russian Training / vCoder.08
Dạng bài
Ngôn ngữ cho phép
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

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    I_am_here  đã bình luận lúc 20, Tháng 6, 2023, 15:38

    ai cho xin thuật toán được không ạ:(((


    • 4
      z  đã bình luận lúc 21, Tháng 6, 2023, 3:15 chỉnh sửa

      bài này bạn dijkstra, coi mỗi hoán vị ~{1,2,...,n}~ là một đỉnh của đồ thị, và cạnh là mọi cách swap ~(i,j)~ với ~1 \leq i <j \leq n~ với trọng số là ~C_{ij}~