頂点 \(i\) からちょうど \(k\) 回移動して頂点 \(j\) に行くためのコストの総和を \(c ^ k _ {i,j}\) と書くことにします。 \((i,j)\) で添字づけられた列 \(c ^ k=(c ^ k _ {i,j}) _ {1\le i\le N,1\le j\le N}\) を考えます。 \(c ^ 1=(C _ {i,j}) _ {1\le i\le N,1\le j\le N}\) です。

\(c ^ a\) と \(c ^ b\) が求められているとき、次のようなアルゴリズムによって \(c ^ {a+b}\) を求めることができます。

• はじめ、\(x _ {i,j}\leftarrow\infty\) で初期化する。
• すべての \((i,j,k)\in\lbrace1,2,\ldots,N\rbrace ^ 3\) に対して以下を繰り返す。
  • \(x _ {i,k}\leftarrow\min\lbrace x _ {i,k},c ^ a _ {i,j}+c ^ b _ {j,k}\rbrace\) で更新する。
• \(x\) が求める \(c ^ {a+b}\) である。

これは min-plus 半環での行列積と考えることもできます。

このアルゴリズムを使うことで、繰り返し二乗法によって答えを \(O(N ^ 3\log K)\) 時間で求めることができます。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>

int main() {
    using namespace std;
    unsigned N, K;
    cin >> N >> K;
    vector C(N, vector<unsigned long>(N));

    for (auto&& row : C)
        for (auto&& c : row)
            cin >> c;

    // a 回移動した結果と b 回移動した結果から a + b 回移動した結果を求める
    const auto prod{[N, inf{ranges::max(C | views::join) * K}](const auto& lhs, const auto& rhs) {
        // 十分大きな値で初期化しておく
        vector ret(N, vector(N, inf));
        for (const auto i : views::iota(0U, N))
            for (const auto j : views::iota(0U, N))
                for (const auto k : views::iota(0U, N))
                    ret[i][k] = min(ret[i][k], lhs[i][j] + rhs[j][k]);
        return ret;
    }};

    auto ans(C);
    --K;

    // 繰り返し二乗法
    while (K) {
        if (K & 1)
            ans = prod(ans, C);
        C = prod(C, C);
        K /= 2;
    }

    for (const auto i : views::iota(0U, N))
        cout << ans[i][i] << endl;
    return 0;
}