FC - MAZE

Source: FC89 - MAZE
Tags: Dynamic Programming, Matrix Multiplication, Graph

Problem:
Cho một đa đồ thị N đỉnh có hướng có khuyên, các cung có trọng số dương, tại mỗi bước có thể thực hiện thao tác đảo trọng số cạnh tiếp theo trong 1 lượt (trọng số c[i] đảo thành -c[i]). Được thực hiện tối đa K lượt đảo trọng số, hãy tìm cách đi sao cho tổng trọng số trên đường đi từ 1 đến N là nhỏ nhất có thể.
N ≤ 50. M ≤ N * (N - 1) / 2. c[i] ≤ 1e5. 0 ≤ K ≤ 1e9.

Ví dụ:
Input:
3 6
1 2 1
1 3 5
2 1 1
2 3 10
3 1 1
3 2 1
1

Output:
-9

Explanation:
Đảo trọng số ở đường đi 2 → 3.

Solution:
Với K = 0, ta có thể giải dễ dàng bài toán bằng thuật toán Floyd.
Với K = 1, ta có thể giải bằng một công thức DP đơn giản như sau:
a[u][v] = min(f[u][e.u] - e.c + f[e.v][v]), trong đó u, v là 2 đỉnh đang xét tìm độ dài đường đi ngắn nhất nếu đảo trọng 1 lần, f[u][v] là độ dài đường đi ngắn nhất từ u đến v khi chưa xài lượt đảo trọng nào (tức K = 0), cũng có nghĩa là mảng Floyd của chúng ta, e.u và e.v là 2 đỉnh trong cung đang xét đảo trọng, tức là nếu đảo trọng cung e thì ta sẽ có tổng trọng là f[u][e.u] - e.c + f[e.v][v], e.c là trọng số cung e.
Với K > 1 bất kỳ, ta có thể sử dụng công thức như sau: a[K][u][v] = min(a[1][u][x] + a[K - 1][x][v]). Công thức này có nghĩa là, để tìm tổng trọng nhỏ nhất từ u đến v sau K lượt sử dụng đảo trọng, ta đảo trọng 1 lần từ u đến x và đảo trọng K - 1 lần từ x đến v.
Từ đây ta có thể thấy công thức trên tuyến tính, do đó để có thể giải với K lớn, ta có thể sử dụng nhân ma trận để tối ưu.
Độ phức tạp: O(N^3 * log(K))

Code: (bình thường mình hay code lũy thừa nhanh bằng đệ quy, cơ mà trong bài này không hiểu vì sao lại ra sai, do đó mình phải code lũy thừa nhanh bằng phương pháp khử đệ quy, cách này mình khuyến khích các bạn nên xài khi đã nằm lòng hoặc đã hoàn thiện bài làm của mình, chứ nếu không lại ngồi nhìn nó cả buổi không làm được bài thì chết. Code của mình lần này hơi theo hướng OOP một chút)
#include <iostream>
#include <vector>
#include <string.h>

using namespace std;

#define fi first
#define se second

int n, m, k, f[55][55];
vector <pair <pair <int, int>, int>> e;

struct matrix {
    long long data[55][55];
    
    void reset() {
        memset(data, 20, sizeof data);
    }
    
    matrix operator *(const matrix &a) {
        matrix res; res.reset();
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                for (int k = 1; k <= n; ++k)
                    res.data[i][j] = min(res.data[i][j], data[i][k] + a.data[k][j]);
        return res;
    }
    
    matrix operator ^(int k) {
        matrix res;
        bool check = true;
        for (; k; k >>= 1, *this = *this * *this)
            if (k & 1)
                res = check ? *this : res * *this,
                check = false;
        return res;
    }
} a;

int main() {
    cin >> n >> m;
    memset(f, 20, sizeof f);
    for (int i = 1; i <= n; ++i)
        f[i][i] = 0;
    for (int u, v, c; m--;)
        cin >> u >> v >> c,
        f[u][v] = min(f[u][v], c),
        e.push_back({{u, v}, c});
    for (int k = 1; k <= n; ++k)
        for (int u = 1; u <= n; ++u)
            for (int v = 1; v <= n; ++v)
                f[u][v] = min(f[u][v], f[u][k] + f[k][v]);
    cin >> k;
    if (!k) {cout << f[1][n]; return 0;}
    a.reset();
    for (int i = 1; i <= n; ++i)
        a.data[i][i] = 0;
    for (int u = 1; u <= n; ++u)
        for (int v = 1; v <= n; ++v)
            for (auto e: e)
                a.data[u][v] = min(a.data[u][v], 1ll * f[u][e.fi.fi] - e.se + f[e.fi.se][v]);
    cout << (a ^ k).data[1][n];
}