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:

~\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);
    }
}