【AtCoder参加記録】ABC226【AB2完】

C問題
https://atcoder.jp/contests/abc226/tasks/abc226_c
に70分ほどかけましたがACできず終了しました。
ABC3完が当面の目標になりそうです。

WAとなったコード

N = int(input())
T = []
K = []
A = []
 
cost = [0]*N
 
for i in range(0, N):
    ls = list(map(int, input().split()))
    T.append(ls[0])
    K.append(ls[1])
    A.append(ls[2:])
    if K[i] == 0:
        cost[i] += T[i]
    else:
        cost[i] = sum([cost[j-1] for j in A[i]]) + T[i]
print(cost[N-1])

解説を見ての実装

N = int(input())
T = []
K = []
A = []
 
for i in range(0, N):
    ls = list(map(int, input().split()))
    T.append(ls[0])
    K.append(ls[1])
    a = [j-1 for j in ls[2:]]
    A.append(a)
 
 
used = [False]*N
used[N-1] = True
ans = 0
for i in reversed(range(N)):
    if used[i]:
        ans += T[i]
        for j in range(K[i]):
            used[A[i][j]] = True
print(ans)

アルゴリズム実技検定公式テキストの深さ優先探索のコードを応用。
https://github.com/kenkoooo/pastbook-source-code/blob/master/chukyu/python/chapter06/section03/6-3-2.py

import sys
sys.setrecursionlimit(1000000)
N = int(input())
T = []
K = []
A = []
 
for i in range(0, N):
    ls = list(map(int, input().split()))
    T.append(ls[0])
    K.append(ls[1])
    a = [j-1 for j in ls[2:]]
    A.append(a)
 
visited = [False]*N
ans = 0
# 再帰関数 dfs を定義する。
def dfs(i):
    global ans
    visited[i] = True
    ans += T[i]            
    for i2 in A[i]:
        if not visited[i2]:            
            dfs(i2)
dfs(N-1)
 
print(ans)

Nを始点としたグラフと考えれば良いという問題だったようです。