解説

まずサンプル 1 を図示してみます。

正解となる通り方をするとこうなります。

このように、辺を何度も通ることでスコアを稼ぐことができます。

$T, N$ が $T, N \le 100$ と小さいので、時刻が $0, 1, 2, \ldots, T$ のとき、それぞれの頂点における最大スコアを求めることを考えてみましょう。

$\text{dp}[i][j]$ を、時間 $i$ のときに地点 $i$ にいる場合の最大のスコアと定義します。

更新は以下のように行います。

$\text{dp}[i][B_k] = \max\{ \text{dp}[i][B_k], \text{dp}[i - 1][A_k] + S_k \}$

$\text{dp}[i][j] = \max\{ \text{dp}[i][j], \text{dp}[i - 1][j] \}$

このようにすることで、 $O((N + M)T)$ で解くことができました。