Editorial for Matrix Exponentiation - Min Path


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: ncduy0303 , chrome

Kí hiệu ~A~ là ma trận kề của đồ thị.

Hãy đi từ ý tưởng đơn giản nhất, gọi ~dp[u][i]~ là đường đi ngắn nhất từ bất cứ đỉnh nào đến đỉnh ~u~ trong ~i~ bước. Dễ thấy, ta có công thức chuyển trạng thái là: ~dp[u][i] = \min_{0 \le v < n}(dp[v][i-1] + A[v][u])~.

Thuật toán này có độ phức tạp ~O(K\times M)~, không thể xử lý được với giới hạn ~10^9~ của ~k~.

Tương tự như bài Count Paths, ta sử dụng thuật toán Nhân ma trận để cải tiến. Tuy nhiên, ta sẽ thay phép nhân và phép cộng trong phép nhân ma trận thông thường lần lượt bởi phép cộng và phép lấy min.

Gọi ~dp_i~ là vector mà phần tử thứ ~u~ là đường đi ngắn nhất trong ~i~ bước và kết thúc tại ~u~ (nói cách khác ~dp_i[u] = dp[u][i]~ theo công thức QHĐ bên trên). Từ ý tưởng QHĐ, ta có: ~dp_{i + 1} = A \times dp_i~, vậy ta cũng có được:

~\begin{array}{lcl} dp_n &=& A \times dp_{n - 1} \\ &=& A \times A \times dp_{n - 2} \\ &=& A \times A \times A \times dp_{n - 3}\\ & = &... = A^n \times dp_0 \end{array}~
Với ~dp_0~ là ma trận: ~\begin{bmatrix} 0 \\ 0 \\ 0 \\ ... \\ 0 \end{bmatrix}~

~\rightarrow~ Ta có ý tưởng lũy thừa ma trận bằng ~\log\ k~ lần nhân ma trận.

Độ phức tạp: ~O(N^3 \times log\ k)~

Code tham khảo

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 2e18L + 5;
int n;
#define REP(i) for(int i = 0; i < n; i++)
struct Matrix {
    vector<vector<ll>> a = vector<vector<ll>>(n, vector<ll>(n, INF));
    Matrix operator *(Matrix other) {
        Matrix product;
        REP(i) {
            REP(j) {
                REP(k) {
                    product.a[i][k] = min(product.a[i][k], a[i][j] + other.a[j][k]);
                }
            }
        }
        return product;
    }
};
Matrix expo_power(Matrix a, long long k) {
    Matrix res = Matrix();
    for(int i = 0; i < n; ++i) {
        res.a[i][i] = 0;
    }
    while(k) {
        if(k % 2) {
            res = res * a;
        }
        k /= 2;
        a = a * a;
    }
    return res;
}
int main() {
    int m, k;
    scanf("%d%d%d", &n, &m, &k);
    Matrix single;
    while(m--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        single.a[a-1][b-1] = c;
    }
    Matrix total = expo_power(single, k);
    ll answer = INF;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            answer = min(answer, total.a[i][j]);
        }
    }
    if(answer > INF / 2) {
        puts("IMPOSSIBLE");
    }
    else {
        printf("%lld\n", answer);
    }
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.