현재 건물까지 건설하려면 이전 건물을 모두 지어야 합니다.

$i$번째 건물까지 짓는 시간을 $\mathrm{total}\left(i\right)$, $i$번째 건물을 짓는 데 걸리는 시간을 $t_i$, $i$번째 건물 이전에 지어야 하는 건물들의 번호 집합을 $\mathcal{D}_i$라 하면

$$ \mathrm{total}\left(i\right)=\begin{cases} t_i & \left(\mathcal{D}_i = \varnothing\right) \\ t_i + \underset{j\in\mathcal{D}_i}{\mathrm{max}}\left(t_j\right) & \mathrm{otherwise.} \end{cases} $$

따라서 각 건물을 깊이 우선 탐색하면서 $\mathrm{total}\left(i\right)$의 값을 저장해 두는 동적 계획법 풀이를 생각할 수 있습니다.

최댓값을 계산하기 위해 모든 건설 순서 규칙을 최대 한 번씩만 확인하므로 시간복잡도는 $O\left(K\right)$입니다.

코드
fn dfs_cache(building: &[(u32, Vec<usize>)], cache: &mut [u32], root: usize) {
    if building[root].1.is_empty() {
        cache[root] = building[root].0;
    } else {
        let mut max_before = 0;
        for &before in &building[root].1 {
            if cache[before] == u32::MAX {
                dfs_cache(building, cache, before);
            }
            max_before = max_before.max(cache[before]);
        }
        cache[root] = max_before + building[root].0;
    }
}

fn solve(building: &[(u32, Vec<usize>)], last: usize) -> u32 {
    let mut cache = [u32::MAX; 1000];
    dfs_cache(building, &mut cache, last);
    cache[last]
}