Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 226 C 問題 Martial artist

AtCoder ABC ABC226 C問題 300 pts

問題

提出解答

問題の概要

技 $1, \dots,$ 技 $N$ の $N$ 個の技がある. 高橋君が技 $i$ を取得するのには $T_i$ 秒かかる. また, 技 $T_i$ を覚えるためには, $K_i$ 個の技 $A_{i,1}, \dots, A_{i,K_i}$ を先に取得していなければならない. ただし, $A_{i,j} \lt i$ である.

技 $N$ を取得するためには最小何秒必要か?

制約

$1 \leq N \leq 2 \times 10^5$
$0 \leq K_i \lt i$
$1 \leq A_{i,j} \lt i~(j=1,2,\dots,K_i)$
$A_{i,1}, \dots, A_{i,K_i}$ は全て異なる
$K_1+\dots+K_N \leq 2 \times 10^5$
$1 \leq T_i \leq 10^9$

解法

技 $N$ を取得するために最低限取得しなければならない技を求めたい. そこで, 以下のような有向グラフ $D=(V,A)$ を作る.

$\displaystyle V=\{1,2,\dots,N\}, \quad A=\bigcup_{i=1}^N \left\{\overrightarrow{iA_{i,j}} \middle | j=1, \dots, K_i \right \}$

このとき, 技 $i$ が技 $N$ を最低限取得しなければならない技であることと, $D$ 上で, $i$ は $N$ から到達可能な頂点であることは必要十分条件である.

よって, $D$ 上で $N$ から到達可能な頂点全てを $i_1, \dots, i_L$ としたとき, 求めるべき答えは

$T_{i_1}+\dots+T_{i_L}$

である. この $i_1, \dots, i_L$ は, BFS (DFS) で求めることができる.