この問題は行列累乗により解くことができます。

街 \(i\) から街 \(j\) への道が存在しないとき、代わりに「魔力値 \(0\) の道路が存在する」としても答えは変化しません（存在しない道を通る経路の魔力は \(0\) になり、答えに影響しないため）。よってそのように仮定します。

\(A_{i,j}\) を街 \(i\) から街 \(j\) への道の魔力値とします。

\(f_k(i,j)\) を「ちょうど \(K\) 本の道を通って街 \(i\) から街 \(j\) へ行く経路の魔力の総和」と定めます。求める答えは \(f_K(1,N)\) です。

ところで、「最後に街 \(j\) に移動する直前にどの街にいたか」を考えることで、 \(f_K(i,j)=\sum_{m=1}^{N}f_{K-1}(i,m)A_{m,j}\) となることがわかります。

よって、行列 \(F_k\) 及び \(A\) を

\(F_k=\begin{pmatrix} f_k(1,1) & \dots & f_k(1,N) \\ \dots &\dots &\dots \\ f_k(N,1) & \dots & f_k(N,N) \\ \end{pmatrix}\)

\(A=\begin{pmatrix} A_{1,1} & \dots & A_{1,N} \\ \dots &\dots &\dots \\ A_{N,1} & \dots & A_{N,N} \\ \end{pmatrix}\)

と定めると、\(F_k = F_{k-1}A\) となり、明らかに \(F_1=A\) であることから、\(F_k=A^k\) となります。よって求める答え \(f_K(1,N)\) は \(A^K\) の \((1,N)\) 成分です。

行列積の計算は定義通り行うことで \(O(N^3)\) でできるので、繰り返し二乗法により \(O(N^3\log K)\) で \(A^K\) を求めることができます。

実装例 (C++)

#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint = atcoder::modint998244353;
using mat = vector<vector<mint>>;

mat matmul(mat x, mat y){
  int n = x.size();
  int m = y.size();
  int l = y[0].size();
  mat ret(n, vector<mint>(l));
  for(int i=0; i<n; i++){
    for(int j=0; j<m; j++){
      for(int k=0; k<l; k++){
        ret[i][k] += x[i][j] * y[j][k];
      }
    }
  }
  return ret;
}

mat matpow(mat a, int k){
  int n = a.size();
  mat ret(n, vector<mint>(n));
  for(int i=0; i<n; i++){
    ret[i][i] = 1;
  }
  while(k){
    if(k&1){
      ret = matmul(ret, a);
    }
    a = matmul(a, a);
    k /= 2;
  }
  return ret;
}

int main(){
  int n, m, k;
  cin >> n >> m >> k;
  mat a(n, vector<mint>(n));

  for(int i=0; i<m; i++){
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    a[u][v]=w;
  }

  auto b = matpow(a, k);
  cout << b[0][n-1].val() << endl;
}

実装例 (Python)

MOD = 998244353

def matmul(x, y):
  n = len(x)
  m = len(y)
  l = len(y[0])
  ret = [[0] * l for _ in range(n)]
  for i in range(n):
    for j in range(m):
      for k in range(l):
        ret[i][k] += x[i][j] * y[j][k]
        ret[i][k] %= MOD
  return ret

def matpow(a, k):
  n = len(a)
  ret = [[0] * n for _ in range(n)]
  for i in range(n):
    ret[i][i] = 1
  while k:
    if k & 1:
      ret = matmul(ret, a)
    a = matmul(a, a)
    k //= 2
  return ret

def main():
  N, M, K = map(int, input().split())
  a = [[0] * N for _ in range(N)]
  for i in range(M):
    U, V, W = map(int, input().split())
    U -= 1
    V -= 1
    a[U][V] = W
  b = matpow(a, K)
  print(b[0][-1])

main()