解説

DP の遷移は行列として表すことができ、行列累乗によって解くことができます。

このとき、通常の行列とは違い、和を $\max$ 、積を $+$ として定義します。これは半環になるため行列の形で計算できます。

時刻 $t$ のときの頂点 $v$ のスコアを $S_{tv}$ とすると、遷移行列 $A$ を使って次のように表すことができます。

$\begin{bmatrix} S_{t1} \\\ S_{t2} \\\ \vdots \\\ S_{tN} \end{bmatrix} = A^t \begin{bmatrix} S_{01} \\\ S_{02} \\\ \vdots \\\ S_{0N} \end{bmatrix}$

初期値は $S_{01} = 1,\quad S_{0v} = -\infty \quad (2 \le v \le N)$ となります。

遷移行列 $A$ は以下のように定義されます。

$A_{ii} = 0$ : これは時間が経った時同じ頂点にとどまってもいいからです。

$A_{B_i A_i} = C_i$ : これは辺による移動です。

答えは $S_{TN}$ となるため、 $O(N^3 \log T)$ で解くことができました。

……行列累乗するには少し $N$ が大きすぎたので、反省です。