FOJ 2173 Nostop：矩陣快速冪求恰走 K 步最短路

問題描述

給定有向圖，N 個節點（N ≤ 50），M 條邊，每條邊有長度。求從節點 1 到節點 N 恰好走 K 步 的最短路徑長度。若不存在輸出 -1。多測試案例。

核心思想：鄰接矩陣乘法重載 + 快速冪

矩陣定義

令 mat[i][j] 表示從 i 到 j 恰走 L 步 的最短距離。初始矩陣 base 為 1 步 最短距離（即鄰接矩陣，無邊處為 INF）。

矩陣乘法重載（Min-Plus 乘法）

定義矩陣乘法 C = A ⊗ B 為：

C[i][j] = min over k ( A[i][k] + B[k][j] )

意義：A 存「走 a 步最短距」，B 存「走 b 步最短距」，則 C 存「走 a+b 步最短距」。這正是動態規劃轉移的矩陣形式。

快速冪

利用二進制分解 K，對 base 矩陣進行快速冪運算，得到 base^K，其 [1][N] 即為答案。

程式碼實現（C++）

/* FOJ 2173 Nostop - Matrix Fast Power for Exact K Steps */
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = 1e17;
const int MAXN = 55;

struct Matrix {
    ll a[MAXN][MAXN];
    int n;
    Matrix(int _n = 0, bool ident = false) : n(_n) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                a[i][j] = (ident && i == j) ? 0 : INF;
    }
};

Matrix multiply(const Matrix& A, const Matrix& B) {
    Matrix C(A.n);
    for (int i = 1; i <= A.n; ++i)
        for (int j = 1; j <= A.n; ++j) {
            ll best = INF;
            for (int k = 1; k <= A.n; ++k)
                if (A.a[i][k] < INF && B.a[k][j] < INF)
                    best = min(best, A.a[i][k] + B.a[k][j]);
            C.a[i][j] = best;
        }
    return C;
}

Matrix quick_pow(Matrix base, long long exp) {
    Matrix res(base.n, true); // 單位矩陣：0步從i到i距離0，其餘INF
    while (exp > 0) {
        if (exp & 1) res = multiply(res, base);
        base = multiply(base, base);
        exp >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n, m; long long k;
        cin >> n >> m >> k;
        Matrix base(n);
        for (int i = 0; i < m; ++i) {
            int u, v; ll w;
            cin >> u >> v >> w;
            base.a[u][v] = min(base.a[u][v], w); // 可能有重邊
        }
        Matrix ans = quick_pow(base, k);
        if (ans.a[1][n] >= INF) cout << -1 << "\n";
        else cout << ans.a[1][n] << "\n";
    }
    return 0;
}

關鍵點解析

• Min-Plus 半環：將「加法」替換為 min，「乘法」替換為 +，構成半環，矩陣乘法結合律成立，故可用快速冪。
• 單位矩陣：對角線為 0（0 步從 i 到 i 距離 0），其餘 INF。乘法時 res = res ⊗ base 正確累積步數。
• INF 選擇：1e17 足夠大（最大路徑長 ≈ 10000 × 50 × 10⁹ < 1e17），避免溢位。
• 重邊處理：初始矩陣取最小權重。

複雜度分析

• 矩陣乘法：O(N³)，N ≤ 50 → 125,000 次操作
• 快速冪：O(log K) 次乘法，K 可大至 10¹⁸
• 總體：O(N³ log K) ≈ 125,000 × 60 ≈ 7.5×10⁶，極快。

總結

FOJ 2173 展示了矩陣快速冪在圖論最短路變體中的威力。「恰走 K 步」限制使得普通 Dijkstra/Floyd 不直接適用，但將 DP 轉移寫成 Min-Plus 矩陣乘法，即可用 O(N³ log K) 高效求解。此技巧同樣適用於「恰走 K 步路徑計數」（將 min 換為 +，+ 換為 ×）等問題。