Maximum Merit Move

解説

まず、「$1$ 回前にいた頂点へ戻れない」という条件がない場合を考えます。

$dp_{k,v}$ を、頂点 $1$ から $k$ 回移動して頂点 $v$ にいるときの最大スコアとすると、頂点 $v$ の隣接頂点を $u$ として、$dp_{k+1,v}=\max_u dp_{k,u}+S_v$ と更新できます。

しかし、今回は直前にいた頂点へ戻ることが禁止されています。そのため、現在の頂点だけでなく、直前の頂点も覚える必要があります。

有向辺 $(u,v)$ に対して、$dp_k(u,v)$ を「頂点 $1$ から $k$ 回移動し、最後に $u\to v$ と移動したときの最大スコア」とします。到達不可能な状態は $-\infty$ とします。

最初の移動について、頂点 $1$ と隣接する頂点 $v$ に対して $dp_1(1,v)=S_v$ とします。

最後に $u\to v$ と移動した後、次に $v\to w$ と移動することを考えます。直前にいた頂点へ戻れないため、$u\neq w$ である必要があります。よって、遷移は

$$dp_{k+1}(v,w)=S_w+\max_{u\in\operatorname{adj}(v),\,u\neq w}dp_k(u,v)$$

となります。

この式をそのまま計算すると、各辺 $(v,w)$ について $v$ のすべての隣接頂点を調べるため、計算量は次数の二乗に依存してしまいます。

そこで、各頂点 $v$ について、$dp_k(u,v)$ の値が大きい方から $2$ 個を管理します。

頂点 $v$ から $w$ へ移動するとき、最大値を与える直前の頂点が $w$ でなければ、その最大値を使えます。一方、最大値を与える直前の頂点が $w$ なら、その状態から $w$ へ戻ることはできないため、$2$ 番目に大きい値を使います。

除外される候補は直前の頂点が $w$ である状態だけなので、最大値と第 $2$ 最大値を持てば十分です。

各移動回数について、まずすべての有向辺 $(u,v)$ を調べて、各頂点 $v$ に到達する状態の最大値と第 $2$ 最大値を求めます。その後、各有向辺 $(v,w)$ について、使用可能な方の値に $S_w$ を加えて次の状態を更新します。

$T$ 回移動した後の頂点 $x$ の答えは、$x$ に到達するすべての状態の最大値です。すべて到達不可能なら $0$ を出力します。到達可能な経路の最大スコアが負の場合は、その負の値をそのまま出力することに注意してください。

時間計算量は $O(TM)$ です。