問題概要
$1$ から $n$ の合計 $n$ ステージからなるゲームをプレイしている．最初，ステージ $1$ のみを遊ぶことができる．
プレイ可能なステージ $i = 1, 2, \dots, n - 1$ では，以下の内 1 つを行うことができる：
- $A_i$ 単位時間かけてステージ $i$ をクリアし，結果，ステージ $i + 1$ が遊べるようになる．
- $B_i$ 単位時間かけてステージ $i$ をクリアし，結果，ステージ $X_i$ が遊べるようになる．
ステージをクリアするのにかかる時間以外は無視できるとき，ステージ $n$ を遊べるようになる時刻は最短でいくらか？
制約
- $2 \leq n \leq 2 \times 10^5$
- $1 \leq A_i, B_i \leq 10^9$
- $1 \leq X_i \leq n$
解法
ステージ $i$ をクリアする行為を，「$A_i$ 時間（resp. $B_i$ 時間）かけてステージ $i + 1$ （resp. ステージ $X_i$）に移動する」ことだと捉え直すと，集合 $V = \{ 1, 2, \dots, n \}$ を頂点集合とする重み付き有向グラフに見えてきます．辺集合についてはコスト関数を簡単に書くために，ちょっと変則的ですが $E = \{ ( i, i + 1, 1 ) \mid i \in V \} \cup \{ ( i, X_i, 2 ) \mid i \in V \}$ として順序対 $( u, v, * )$ ($u, v \in V$) を有向辺 $( u, v )$ と同一視します．これで，コスト関数 $w$ は
\begin{equation*}
w( ( u, v, t ) ) = \begin{cases}
A_u & \text{($t = 1$)} \\
B_u & \text{($t = 2$)}
\end{cases}
\end{equation*}
と定義でき*1，重み付きグラフ $( V, E, w )$ を作れます．元の問題は，このグラフにおける頂点 $1 \in V$ から頂点 $n \in V$ への最短経路を求めることに対応します．
重み付きグラフの最短経路を求めるアルゴリズムのひとつとして Dijkstra 法が知られていて，この問題も Dijkstra 法で解けるということになります*2．
計算量については順位キューを使った実装で $O( |E| \log |V| )$ 時間になるとよく言われます[誰によって？]が，この問題の場合は各頂点から伸びる辺が高々（正の）定数本なので辺の総数は $\Theta( |V| )$ 本です．すると $\Theta( |V| ) = \Theta( |E| )$ となり*3，全体の計算量は $O( |V| \log |V| )$ 時間となります．
コード
constexpr auto INF = LIM< LL >::max() / 2; int main() { IN( int, N ); VI A( N - 1 ), B( N - 1 ), X( N - 1 ); REP( i, N - 1 ) { cin >> A[i] >> B[i] >> X[i]; --X[i]; } static LL distances[ 1 << 18 ]; fill( AALL( distances ), INF ); distances[0] = 0; using State = pair< LL, int >; priority_queue< State, vector< State >, greater< State > > que; que.EM( 0, 0 ); while ( !que.empty() ) { const LL dist = que.top().fst; const int i = que.top().snd; que.pop(); if ( N - 1 <= i ) { continue; } if ( const LL ndist1 = dist + A[i]; chmin( distances[ i + 1 ], ndist1 ) ) { que.EM( ndist1, i + 1 ); } if ( const LL ndist2 = dist + B[i]; chmin( distances[ X[i] ], ndist2 ) ) { que.EM( ndist2, X[i] ); } } cout << distances[ N - 1 ] << endl; return 0; }
