VOJ - V8SORT

Source: V8SORT
Tags: Graph

Problem:
Cho một dãy số, bạn cần sắp xếp lại dãy số bằng cách đổi chỗ các cặp phần tử. Chi phí để đổi chỗ cặp phần tử i và j là C[i][j]. Tìm chi phí nhỏ nhất để sắp xếp dãy số tăng dần.
Số phần tử không vượt quá 7.
0 ≤ C[i][j] ≤ 999.
C[i][i] = 0 và C[i][j] = C[j][i].
Dòng đầu chứa dãy số. Gọi số lượng phần tử của dãy số là N, N dòng sau mỗi dòng chứa N số, số thứ j ở dòng thứ i biểu diễn C[i][j].

Ví dụ:
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

Output:
4

Explanation:
Dãy ban đầu
1 2 3 4 6 5
Đổi phần tử vị trí 4 và 5 (C[4][5] = 1)
1 2 3 6 4 5
Đổi phần tử vị trí 4 và 6 (C[4][6] = 2)
1 2 3 5 4 6
Đổi phần tử vị trí 4 và 5 (C[4][5] = 1)
1 2 3 4 5 6

Solution:
Ta có thể giải quyết bài này bằng cách coi các trạng thái của mảng sau các lần swap là một đỉnh rồi sau đó Dijkstra. Từ một trạng thái ta có C(2, N) cạnh nối tới các trạng thái khác, từ đó Dijkstra từ cấu hình ban đầu từ cấu hình kết thúc (đã sort tăng dần). Để có thể lưu trạng thái, ta nén số lại, vì số phần tử tối đa chỉ có 7 nên có thể lưu dưới dạng số thập phân 7 chữ số (hoặc hệ thất phân cho đỡ tốn bộ nhớ :>).
Độ phức tạp O(N!*log(N!))

Code:
#include <iostream>
#include <algorithm>
#include <sstream>
#include <queue>

using namespace std;

#define ii pair <int, int>

int n, a[7], c[7][7], x;
bool vis[7000000];
priority_queue <ii, vector <ii>, greater <ii> > heap;

int state() {
    int res = 0;
    for (int i = 0; i < n; i++)
        res = res * 7 + a[i];
    return res;
}

int main() {
    string s; getline(cin, s);
    stringstream ss(s);
    while (ss >> a[n++]); --n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> c[i][j];
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int j = 0; j < n; j++)
            cnt += a[i] > a[j];
        x = x * 7 + cnt;
    }
    heap.push({0, x});
    for (int i = n - 1; i >= 0; i--)
        a[i] = x % 7, x /= 7;
    sort(a, a + n);
    x = state();
    while (!heap.empty()) {
        int p = heap.top().first;
        int u = heap.top().second;
        heap.pop();
        if (u == x) {
            cout << p; return 0;
        }
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = n - 1; i >= 0; i--)
            a[i] = u % 7, u /= 7;
        for (int i = 0; i < n - 1; i++)
            for (int j = i + 1; j < n; j++)
                swap(a[i], a[j]),
                heap.push({p + c[i][j], state()}),
                swap(a[i], a[j]);
    }

}